Search in Rotated Sorted Array (LeetCode 33)

The problem

An array of distinct integers was sorted in ascending order and then rotated at an unknown pivot, so [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2]. Given this array and a target, return the target’s index, or -1 if it is not present. It must run in O(log n).

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4

0 is at index 4, just after the rotation point.

How to think about it

Start with brute force. A linear scan is O(n) and ignores the structure. Another idea is to first find the pivot with one binary search, then run a normal binary search on the correct side. That works in O(log n) but needs two searches and two sets of index arithmetic.

Normal binary search breaks here. Seeing nums[mid] = 7 and target = 0, a plain search would go left because 0 < 7. But 0 is on the right. Comparing with mid alone no longer tells you which side the target is on.

The key insight: at least one half around mid is always fully sorted. The rotation point can only be in one half. So compare nums[lo] with nums[mid]. If nums[lo] <= nums[mid], the left half [lo..mid] is sorted. Otherwise the right half [mid..hi] is sorted. In a sorted half you can test membership with two comparisons: is nums[lo] <= target < nums[mid]? If yes, search there; if not, the target must be in the other half. Either way you discard half the range.

Which pattern is this? Binary search on a modified sorted array. The tell is “rotated sorted array” plus “O(log n)“. The habit to build: find the half you can reason about, decide using it, and discard.

Approach

1. Set lo = 0, hi = len(nums) - 1.
2. 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], set hi = mid - 1; else lo = mid + 1.
   • Else (right half sorted): if nums[mid] < target <= nums[hi], set lo = mid + 1; else hi = mid - 1.
3. Return -1.

Solution

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 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
# search_rotated([4,5,6,7,0,1,2], 0) -> 4
# search_rotated([4,5,6,7,0,1,2], 3) -> -1

Dry run

On nums = [4, 5, 6, 7, 0, 1, 2], target = 0:

The answer is 4. For target = 3, the range shrinks to lo = 7, hi = 6 and the function returns -1.

Complexity

• Time: O(log n). Each step discards half of [lo, hi].
• Space: O(1).

Edge cases and pitfalls

• <= in nums[lo] <= nums[mid] matters when lo == mid (a range of one or two elements). With <, the code wrongly treats a one-element left half as unsorted.
• Boundary comparisons: the sorted-half tests are half-open on the mid side (target < nums[mid], nums[mid] < target) because mid was already checked.
• No rotation (already sorted) works: the left half is always sorted and the logic reduces to plain binary search.
• Single element and target absent both end with an empty range and -1.
• Duplicates break this version: with [1, 0, 1, 1, 1] you can’t tell which half is sorted. That is LeetCode 81, which needs a lo += 1 fallback and is O(n) in the worst case.

Related problems

• Find Minimum in Rotated Sorted Array (LeetCode 153): find the rotation point itself.
• Binary Search (LeetCode 704): the base template this extends.
• Find Peak Element (LeetCode 162): another binary search where the array isn’t sorted, but local structure tells you which half to keep.