Search in Rotated Sorted Array

Hints

1. Two-pass approach. Find the pivot first (the index of the smallest element), then binary-search the appropriate half. Two binary searches, still O(log n), but extra code.
2. One-pass approach (better). At each midpoint, decide which half is sorted by comparing endpoints. Then decide whether the target lies in the sorted half (using value bounds) or the rotated half.
3. Which half is sorted? If nums[lo] ≤ nums[mid], the left half [lo, mid] is sorted. Otherwise the right half [mid, hi] is sorted. Exactly one of these is true at every iteration.
4. Where does the target lie? If the left half is sorted and nums[lo] ≤ target < nums[mid], the target is in the left half; otherwise in the right. Symmetric logic for the right-sorted case.
5. Boundary discipline. Use the half-open [lo, hi) convention or be very careful with inclusive bounds. Off-by-one is the classic failure mode of this problem.
6. What if duplicates are allowed? The endpoint-comparison trick can fail when nums[lo] == nums[mid] == nums[hi]. Worst case becomes O(n). The "Search in Rotated Sorted Array II" variant addresses this.

Solution, one-pass binary search

The key observation

A rotated sorted array of distinct values has the property that at every midpoint, at least one of the two halves is sorted. The pivot lies in the other half. By determining which half is sorted and whether the target lies within its bounds, we can eliminate one half per iteration, preserving O(log n).

Approach 1 · Two-pass. O(log n)

Find the pivot via binary search; then run a second binary search on the sorted half containing the target. Conceptually simple; double the boundary-juggling.

Approach 2 · One-pass with inline pivot logic. O(log n)

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

The branching: nums[lo] ≤ nums[mid] is the test for "left half is sorted." If it's true, we know the left half is a contiguous ascending range from nums[lo] to nums[mid]. The target lies in that range iff nums[lo] ≤ target < nums[mid]. The inequality is non-strict on the left (we already checked nums[mid] == target) and strict on the right (target can equal nums[lo] but if it equals nums[mid] we'd have returned).

The symmetric case: if the left isn't sorted, the right must be. nums[mid] < target ≤ nums[hi] places the target in the sorted right half.

A worked trace

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

iter 1: lo=0, hi=6, mid=3, nums[mid]=7
        nums[lo]=4 ≤ nums[mid]=7 → left sorted
        4 ≤ 0 < 7? no → target in right
        lo = 4

iter 2: lo=4, hi=6, mid=5, nums[mid]=1
        nums[lo]=0 ≤ nums[mid]=1 → left sorted
        0 ≤ 0 < 1? yes → target in left
        hi = 4

iter 3: lo=4, hi=4, mid=4, nums[mid]=0
        return 4

Complexity comparison

Edge cases to verify

• Array not rotated. Reduces to standard binary search; the algorithm handles it as a special case (left half is always sorted).
• Target equals an endpoint. nums = [1, 3], target = 3: mid = 0, nums[mid] = 1, target in right → lo = 1, return 1.
• Single element. Loop runs once; either match or return −1.
• Pivot at index 0. Array is fully sorted; left half always sorted.
• Pivot at index n − 1. Last element is smaller than first; the test nums[lo] ≤ nums[mid] still holds for the initial midpoint.

Where beginners go wrong

• Using strict inequality on the wrong side. nums[lo] ≤ target < nums[mid], the lower bound is non-strict because target could equal nums[lo], but the upper bound is strict because nums[mid] was already checked. Flipping either inequality drops valid targets at the boundaries.
• Picking the wrong "sorted" test. nums[lo] ≤ nums[mid] tests whether the left half is sorted. nums[mid] ≤ nums[hi] tests the right. Use one consistently; mixing introduces bugs.
• Off-by-one on lo = mid + 1 vs hi = mid - 1. The standard inclusive-bound binary search uses both; the half-open form uses hi = mid with no minus one. Pick a convention and stick with it.
• Assuming the array contains the target. Returning nums[lo] at the end of the loop is wrong if the target isn't present. The post-loop case must return −1.
• Trying to handle duplicates with the same code. Duplicates break the endpoint-comparison invariant, nums[lo] == nums[mid] == nums[hi] is possible and tells you nothing about which half is sorted. The variant problem requires a degenerate-case skip; worst-case becomes O(n).

Interview follow-ups to expect

• "What if duplicates are allowed?" When nums[lo] == nums[mid] == nums[hi], increment lo and decrement hi by one to shrink the search range. Worst case O(n) but average remains O(log n) for most inputs.
• "Find the minimum element instead of a target." Binary search for the pivot, at each step, compare nums[mid] with nums[hi]. If less, the pivot is in [lo, mid]; otherwise it's in (mid, hi]. O(log n).
• "How many times has the array been rotated?" Same as finding the pivot, the rotation count equals the pivot index.
• "Two rotations stacked, a list rotated, then rotated again." Equivalent to one rotation; the original sortedness assumption still holds.
• "What if the array is rotated AND has duplicates?" See the duplicate variant above. Sometimes the interviewer just wants to know you'd handle the degeneration.

Related reading

• Binary Search on the Answer, the broader pattern of which this is a specialisation.
• Sorting & Search, the module that frames binary search's role in algorithm design.