Search in Rotated Sorted Array: Binary Search That Still Works

Take a sorted array, cut it at some index, and swap the two pieces: [2, 3, 6, 9, 12, 15, 18] becomes [12, 15, 18, 2, 3, 6, 9]. Now find 3 in O(log n). Plain binary search fails, because the array is no longer sorted end to end. It does not need to be. One observation rescues the whole algorithm, and once you see it, the code is only a few lines longer than the binary search you already know.

The problem it solves

You are given distinct integers that were sorted in ascending order and then rotated by an unknown amount. Return the index of a target value, or -1 if it is absent.

A linear scan answers in O(n) and ignores everything the input promises. The rotation destroyed global order but kept almost all of it: the array is two sorted runs glued together, with exactly one drop where the largest value is followed by the smallest. The goal is to keep discarding half of the range per step, as binary search does, while the drop sits somewhere unknown.

The intuition

Pick any middle index. The drop is either left of mid, right of mid, or nowhere in the current range. It cannot be on both sides, because there is only one. So at least one half is fully sorted, and one comparison tells you which:

• If nums[lo] <= nums[mid], the values climb all the way from lo to mid, so the left half is sorted.
• Otherwise the drop is on the left, and the right half, mid to hi, is sorted.

A sorted range is easy to reason about: the target lies inside it exactly when it falls between the range's two end values. So check the sorted half. If the target is in it, keep that half; if not, keep the other one. Either way half the range is gone, which is all binary search ever needed.

Notice that you never locate the rotation point first. You only ever ask "which side is clean?", and each answer is local to the current lo, mid and hi.

Watch it run

The animation searches the lesson's array [12, 15, 18, 2, 3, 6, 9] for 3. The first mid lands on the 2 at index 3, right after the drop. The left side contains the drop, so the right side 2, 3, 6, 9 is the sorted one, and 3 falls between its ends: keep it. On the next split the left half 3, 6 is sorted and contains 3. Then mid lands on the target. Three probes for seven values.

The code

The search itself. The only change from ordinary binary search is the if that decides which half is sorted; inside each branch the test is a plain range check:

def search_rotated(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 lo..mid is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1                    # target is inside it
            else:
                lo = mid + 1                    # target is in the other half
        else:                                   # right half mid..hi is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

print(search_rotated([12, 15, 18, 2, 3, 6, 9], 3))    # 4
print(search_rotated([12, 15, 18, 2, 3, 6, 9], 13))   # -1
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))       # 4

A common follow-up asks for the rotation point itself: the index of the minimum, which is also how many places the array was rotated. Compare mid with the right end. If nums[mid] is larger, the drop is to its right; otherwise mid might be the minimum, so keep it:

def find_rotation(nums):
    """Index of the smallest value = how far the array was rotated."""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1                        # the drop is right of mid
        else:
            hi = mid                            # mid could be the minimum
    return lo

print(find_rotation([12, 15, 18, 2, 3, 6, 9]))        # 3
print(find_rotation([1, 2, 3]))                       # 0

With duplicates the "which half is sorted" test can be fooled. In [1, 2, 1, 1, 1], the values at lo, mid and hi are all 1, the left half looks sorted, and the 2 is thrown away. The fix is to shrink both ends by one when all three are equal, because neither end can be the only copy of the target once nums[mid] has been checked:

def search_rotated_dupes(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return True
        if nums[lo] == nums[mid] == nums[hi]:   # cannot tell which side is sorted
            lo, hi = lo + 1, hi - 1
        elif nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return False

print(search_rotated([1, 2, 1, 1, 1], 2))             # -1  (wrong: 2 is at index 1)
print(search_rotated_dupes([1, 2, 1, 1, 1], 2))       # True

All three functions against brute force — list.index, min and in — on 5,000 random rotations of random sorted arrays, including empty arrays, rotations by zero and targets that are absent:

import random

random.seed(12)
ok = True
for _ in range(5000):
    n = random.randint(0, 15)
    base = sorted(random.sample(range(-20, 40), n))  # distinct values
    k = random.randint(0, n) if n else 0
    nums = base[k:] + base[:k]                       # rotate by k
    target = random.randint(-22, 42)
    want = nums.index(target) if target in nums else -1
    ok &= search_rotated(nums, target) == want
    if n:
        ok &= nums[find_rotation(nums)] == min(nums)

    dup = sorted(random.randint(0, 5) for _ in range(n))
    j = random.randint(0, n) if n else 0
    dup = dup[j:] + dup[:j]
    t = random.randint(-1, 6)
    ok &= search_rotated_dupes(dup, t) == (t in dup)
print(ok)                                            # True

The complexity

With distinct values, every iteration discards at least half of the remaining range, so the search is O(log n) time and O(1) space, the same as ordinary binary search. find_rotation is also O(log n).

With duplicates the guarantee is gone. When lo, mid and hi hold equal values, the loop can only shrink the range by one from each end, and an input like [1, 1, 1, 1, 2, 1, 1, 1] can force that on nearly every step. The worst case is O(n), and no algorithm can do better in general: a single different value hidden among equal ones cannot be found without looking at most positions.

Where it goes wrong

• Using < instead of <= in nums[lo] <= nums[mid]. When the range has two elements, lo and mid are the same index. The left half is a single value and is sorted; a strict comparison sends the search into the wrong branch.
• Loose range checks. The sorted-left test is nums[lo] <= target < nums[mid]: inclusive at the end you have not checked, exclusive at mid, which you already have. Swapping the inclusive ends silently skips targets sitting at a boundary.
• Assuming distinct values. The distinct-value version returns wrong answers on duplicates, as the [1, 2, 1, 1, 1] example shows. Ask which input you are getting before you write code.
• Finding the pivot, then searching twice. It works and is still O(log n), but it is two loops and two chances for an off-by-one where one loop suffices.

How to say it in an interview

"A rotated sorted array has exactly one drop, so whenever I split it at mid, at least one half is sorted. I check which one by comparing nums at lo with nums at mid. If the target falls within that sorted half's end values I keep it, otherwise I keep the other half. Each step still discards half, so it's O(log n) time and O(1) space. If the values can repeat, equal values at lo, mid and hi hide the sorted half; I shrink both ends by one, and the worst case becomes O(n)."

The "keep the half that must contain the answer" move is the same one behind finding a peak element, and the boundary-handling details come from binary search variants.