LC 33 · Medium · Template A · half-sorted decision

Search in Rotated Sorted Array

A rotated sorted array where you need to find a specific value, not the pivot.

Recognise it

Before any code, what in the question tells you this is the pattern?

Rotated sorted array + "find target in O(log n)". The combo of "rotated" and "log n" rules out a linear scan and forces a modified binary search. Extremely common phone-screen question.

The brute force

Always have this one ready. It is the honest starting point, and it is what the real solution improves on.

Scan every element and compare it to the target.

O(n) time and O(1) space.

The tempting middle ground is to find the rotation point first with one binary search, then binary search the correct run. That is perfectly correct and stays logarithmic. It is also two passes and two chances to get a boundary wrong, when one pass is enough.

The approach

The idea in plain language, before it becomes syntax.

The key observation is small and does all the work: no matter where you cut a rotated array, at least one of the two halves is fully sorted. The cliff can only sit on one side.

So each step goes in two stages. First work out which half is sorted, by comparing the element at lo against the element at mid. If a[lo] is at most a[mid], the left half is clean. Otherwise the cliff is in the left half and the right half must be clean.

Second, ask whether the target lies inside the sorted half, which is easy because you know both of its endpoints. If it does, throw away the other half and continue there. If it does not, the target can only be in the messy half, so throw the sorted one away. Either way the range halves, which keeps the running time logarithmic.

A rotated array split at mid, showing that one half is always sorted.Split anywhere and one side is always properly sorted.40516273041526midsorted halfthe rotated halfWork out which half is sorted, ask if the target falls inside its range,and throw the other half away.
Search in Rotated Sorted Array: the idea in one picture.edit source

The algorithm

The same idea again, as steps you could follow with a pencil.

Flowchart deciding which half of a rotated array is sorted before halving.a[mid] == target ?yesreturn midnoa[lo] <= a[mid] ?yesleft half is sortedtarget inside [lo, mid) ?noright half is sortedtarget inside (mid, hi] ?keep that halfUse <= in a[lo] <= a[mid]. With two elements, < sends you down the wrong branch.
Search in Rotated Sorted Array: the loop, step by step.edit source
Time O(log n)Space O(1)

The solution

Now the code, and why each decision in it is the way it is.

search_in_rotated_sorted_array
def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:              # left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                   # right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

The comparison a[lo] <= a[mid] uses <= rather than <. When the range narrows to two elements, lo and mid point at the same slot and a strict comparison sends you down the wrong branch.

The range check on the sorted half must also be inclusive on the correct end, because the target can legitimately sit exactly on a boundary. Write the check as a[lo] <= target && target < a[mid] and mirror it for the other side.

Test with a target that is present, one that is absent, an array rotated by zero positions, and one of length two. Those four cases catch essentially every mistake this problem invites.

Why the sorted-half test uses <= rather than <.31lo, midhiwith two elements, lo and mid are the same slota[lo] < a[mid]false, so it picks the wrong halfa[lo] <= a[mid]correct
This is the case that punishes a strict less-than.

Where people slip

  • Test nums[lo] <= nums[mid] (use ≤) to decide the sorted half. The equal case matters when lo==mid.
  • Inside the sorted half use a half-open range check: nums[lo] <= target < nums[mid].
  • This is a decision tree, not a formula. Write it slowly and dry-run one rotated example on the whiteboard.

Your notes

What tripped you up here? Write it in your own words.

Where interviewers go next

Solve this one and the follow-up is usually a variation rather than a new idea. Knowing the connection is worth more than memorising each problem.

  • Search in Rotated II (dupes)LC 81When nums[lo]==nums[mid]==nums[hi] you can't pick a sorted half. Shrink both ends by one. Worst case O(n).
  • Two-pass alternativevariantFind pivot with LC 153, then do a plain binary search on the correct segment. Easier to reason about, same complexity. a valid thing to offer.