Search in Rotated Sorted Array

Search in Rotated Sorted Array takes the comfortable world of binary search and tilts it. The array is still sorted — it has just been rotated at some unknown point. The trick is realizing that half of it is always still sorted, and binary search can live in that half.

The slow way first

You could scan every element and compare it to the target. That finds the answer, but it is O(n) — it ignores all the sortedness we were handed. The problem explicitly asks for O(log n), which is a giant hint: use binary search.

The catch: plain binary search needs a fully sorted array. After rotation, comparing the target to nums[mid] no longer tells us which way to go, because the array dips down at the pivot.

The idea: one half is always sorted

Here is the key observation. Pick any mid. The pivot can only be on one side of it, which means the other side is perfectly sorted. So at every step:

1. Compute mid. If nums[mid] == target, done.
2. Figure out which half is sorted by comparing nums[lo] with nums[mid].
3. In that sorted half, a normal range check tells us whether the target lives there.
4. Keep the half that could contain the target; throw away the other.

Because we still halve the search space every step, the whole thing stays O(log n).

Walk through it

Step through the animation with nums = [4,5,6,7,0,1,2], target = 0. First mid = 3 (value 7): the left half [4,5,6,7] is sorted, but 0 is not inside [4,7], so we move lo past mid. Next mid = 5 (value 1): the left half [0,1] is sorted and 0 is inside [0,1], so we move hi left. Finally mid = 4 (value 0) matches — we return index 4. Three probes, not seven.

Pseudocode

lo, hi = 0, last index
while lo <= hi:
    mid = (lo + hi) // 2
    if nums[mid] == target: return mid
    if the left half (lo..mid) is sorted:        # nums[lo] <= nums[mid]
        if target is in [nums[lo], nums[mid]):  hi = mid - 1
        else:                                   lo = mid + 1
    else:                                        # right half (mid..hi) is sorted
        if target is in (nums[mid], nums[hi]]:  lo = mid + 1
        else:                                   hi = mid - 1
return -1

The Python solution

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 sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                              # right half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

• nums[lo] <= nums[mid] is the heart of it: if true, the left half is sorted; otherwise the right half is.
• Once we know which half is sorted, we use an ordinary range check on its endpoints to decide if the target is inside it.
• The boundaries are exclusive on the mid side (target < nums[mid], nums[mid] < target) because nums[mid] was already tested for equality above.
• Each branch discards half the array, so we loop at most about log2(n) times.

Complexity

We do constant extra work and use no extra memory — just three indices that close in on the answer.

When this pattern shows up

Practice