vizlearn

Search in a rotated sorted array

Interview QuestionsBy Updated

Binary search still works, because after any rotation at least one half is still sorted. Compare the ends to find which, then check whether the target falls inside that half's range: if it does, search there; if not, search the other. Still O(log n).

Overview

Why binary search survives rotation

A rotation splits the array into two sorted runs. Wherever mid lands, it is inside one of them — so at least one of [lo, mid] and [mid, hi] is entirely in order. That is the invariant the whole solution rests on, and it holds for any rotation amount including zero.

values[lo] <= values[mid] identifies which. Use <=, not <: when lo == mid the left half is a single element and is trivially sorted.

Lists & arraysCoding problemMedium

Step through it

What to watch

  • One side of mid is always in order.
  • The decision is about the sorted half's range, not about mid alone.
  • The window halves every step, exactly as in plain binary search.

Say this out loud

"One half is always sorted - compare a[lo] with a[mid] to see which. Then check if the target is inside that sorted half's range and discard accordingly. O(log n), no pre-pass to find the pivot."

Search in a rotated sorted array

A sorted array has been rotated at an unknown pivot. Find a target in O(log n).

The decision that follows

Having found a sorted half, you can test membership by range rather than by searching. If the target lies between that half's endpoints, it can only be there. If it does not, it can only be in the other half. Either way one half is discarded per step.

The bounds matter: values[lo] <= target < values[mid] on the left, and values[mid] < target <= values[hi] on the right. mid has already been compared, so it is excluded on both sides.

The duplicates variant

With duplicates allowed, values[lo] == values[mid] == values[hi] tells you nothing about which half is sorted, and the only safe move is to shrink the window by one. That makes the worst case O(n) — and it is a genuine lower bound, not a lazy implementation.

Saying "O(log n), but O(n) worst case if duplicates are allowed" is the complete answer, and the follow-up interviewers reach for when the first part goes smoothly.

Run it in Python

The search with each decision printed, checked against a linear scan at every rotation of the same array, plus the duplicates variant and its O(n) case.

rotated_search.pyPython 3
Output
How the code works
  1. if values[lo] <= values[mid]:Identifies the sorted half. <= rather than < because when lo == mid the left half is one element, which is sorted.
  2. values[lo] <= target < values[mid]Membership by range, not by search. If the target is inside the sorted half's endpoints it can only be there; otherwise it can only be in the other half.
  3. mid excluded on both sideshi = mid - 1 and lo = mid + 1. mid has already been compared, and leaving it in the window is the usual way to write an infinite loop here.
  4. values[lo] == values[mid] == values[hi]The duplicates case, where nothing can be deduced and the only safe move is to shrink by one. That is what makes the worst case O(n).
Change one thing
  • Rotate by zero — a plain sorted array. The left half is always the sorted one and it degenerates to ordinary binary search.
  • Find the pivot first with its own binary search, then do a normal search in the right run. Two passes, same complexity, and easier to reason about.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. Why does binary search still apply after rotation?
  2. Having identified the sorted half, you decide where to search by:
  3. With duplicates allowed, the worst case becomes:





 Cheat sheet
Search in a rotated sorted array
Binary search still works, because after any rotation at least one half is still sorted. Compare the ends to find which, then check whether the target falls inside that half's range: if it does, search there; if not, search the other. Still O(log n).
INTERVIEW · vizlearn.in/interview/search-in-rotated-sorted-array.html
More in Interview
InterviewSliding window maximumInterviewlist vs tuple vs deque vs array — which and why?InterviewHow does a Python dict work?InterviewWhy must dictionary keys be hashable?
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact