Rotated Sorted Array Search

LeetCode 33, Search in Rotated Sorted Array, sets up a familiar scene with a twist. You have a sorted array of distinct integers, but someone took it and rotated it at some unknown pivot. What was once [0, 1, 2, 4, 5, 6, 7] became [4, 5, 6, 7, 0, 1, 2]. Given a target value, find its index in $O(\log n)$ time, or return -1 if it is not there.

A linear scan works, but it does not use the structure of the input. The array is almost sorted: it is two sorted halves stitched together. Surely binary search should apply. But the rotation breaks the usual invariant: you cannot simply check whether the target is to the left or right of mid, because the values do not increase monotonically from left to right. So the standard binary search fails. The question is how to fix it.

The key insight: one half is always sorted

Here is the observation that makes everything work. Pick any midpoint in a rotated sorted array. The rotation "break", the point where the values jump from the maximum down to the minimum, can only be in one half. That means the other half is perfectly sorted.

More precisely: if nums[lo] <= nums[mid], then the left half [lo..mid] is sorted (no break in it). Otherwise, the right half [mid..hi] is sorted. This is always true, regardless of where the pivot is or where mid lands.

Once you know which half is sorted, you can check whether the target falls within that sorted range. If it does, search there: you have a clean, normal binary search subproblem. If it does not, search the other half. Either way, you cut the search space in half each iteration, maintaining $O(\log n)$ performance.

Walking through an example

Let's search for 0 in [4, 5, 6, 7, 0, 1, 2].

Initial state: lo = 0, hi = 6.

Iteration 1: mid = 3, nums[mid] = 7. Is the target 0? No. Check: nums[lo] = 4 <= 7 = nums[mid], so the left half [4, 5, 6, 7] is sorted. Is 0 in the range [4, 7)? No, since 0 < 4. So the target must be in the right half. Set lo = 4.

Iteration 2: lo = 4, hi = 6, mid = 5, nums[mid] = 1. Is the target 0? No. Check: nums[lo] = 0 <= 1 = nums[mid], so the left half [0, 1] is sorted. Is 0 in the range [0, 1)? Yes, since 0 <= 0 < 1. Search left: set hi = 4.

Iteration 3: lo = 4, hi = 4, mid = 4, nums[mid] = 0. Found the target at index 4.

At every step, we eliminated half the array. The rotation never confused us because we always identified the sorted half first and made our decision based on that.

The code

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        # Determine which half is sorted
        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

Pay close attention to the boundary conditions. The check nums[lo] <= target < nums[mid] uses a non-strict inequality on the left (<=) because the target might equal nums[lo], but a strict inequality on the right (<) because we have already checked whether nums[mid] equals the target. The mirror check for the right half follows the same logic: nums[mid] < target <= nums[hi].

Find Minimum in Rotated Sorted Array

A closely related problem is finding the minimum element, the pivot point where the rotation happened. This is LeetCode 153, and the strategy is a twist on the same idea.

Instead of looking for a specific target, you are looking for the place where the sorted order breaks. The minimum element is the one that is smaller than its predecessor. And here is the key: the minimum must be in the unsorted half. If both halves are sorted, the minimum is simply nums[lo].

Think about it: in a rotated sorted array, the "break" from large values back to small values is where the minimum lives. If the left half is sorted and the right half contains the break, the minimum is somewhere in the right half. So you move toward the unsorted half, the opposite of what you do when searching for a target in the sorted half.

Walking through Find Minimum

Take [3, 4, 5, 1, 2].

Initial state: lo = 0, hi = 4.

Iteration 1: mid = 2, nums[mid] = 5. Compare nums[mid] to nums[hi]: 5 > 2, which means the right half is not sorted, so the break is to the right. Set lo = mid + 1.

Iteration 2: lo = 3, hi = 4, mid = 3, nums[mid] = 1. Compare: 1 <= 2, so the right half is sorted. The minimum could be nums[mid] itself, so set hi = mid.

Iteration 3: lo = 3, hi = 3. Loop ends. The minimum is nums[3] = 1.

The code for Find Minimum

def findMin(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            # Break is in the right half; minimum is to the right of mid
            lo = mid + 1
        else:
            # Right half is sorted; minimum is mid or to the left
            hi = mid
    return nums[lo]

Notice this uses lo < hi (not lo <= hi) and hi = mid (not hi = mid - 1). The reason: when nums[mid] <= nums[hi], the right half is sorted and nums[mid] could be the minimum, so you cannot exclude it. This is the same template used in binary-search-on-answer-space problems: when the midpoint might be the answer, set hi = mid to keep it in range.

The duplicates problem

Everything above assumes distinct elements. LeetCode 81 and LeetCode 154 drop that assumption, and the logic breaks in a specific and frustrating way.

Consider nums = [1, 0, 1, 1, 1] with lo = 0, mid = 2, hi = 4. We have nums[lo] = 1, nums[mid] = 1, and nums[hi] = 1. Is the left half sorted? nums[lo] <= nums[mid] says yes. Is the right half sorted? nums[mid] <= nums[hi] says yes. But the array is clearly not fully sorted: the minimum 0 is hiding in the left half. Neither half gives us reliable information.

When nums[lo] == nums[mid] == nums[hi], you simply cannot determine which half contains the break. The only safe move is to shrink the search space by a constant amount. The standard approach is to increment lo by one (or decrement hi by one) and try again.

def findMin(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        elif nums[mid] < nums[hi]:
            hi = mid
        else:
            # nums[mid] == nums[hi], can't decide; shrink
            hi -= 1
    return nums[lo]

The search-for-target variant with duplicates uses the same escape hatch: when nums[lo] == nums[mid], increment lo to break the tie, then continue the normal logic.

Why duplicates degrade to $O(n)$

In the worst case, every element is the same except one. Picture [1, 1, 1, 1, 0, 1, 1]. At every step, nums[lo] == nums[mid] == nums[hi], so you can only shrink by one element. You end up scanning nearly the entire array before finding the minimum. The worst-case time complexity degrades from $O(\log n)$ to $O(n)$.

There is no way around this. With duplicates, no comparison-based algorithm can guarantee better than $O(n)$ in the worst case, because you might need to inspect every element to distinguish [1, 1, 1, ..., 1] (no rotation) from [1, 1, 0, 1, ..., 1] (rotation present).

In practice, duplicates are rare enough that the algorithm still runs fast on most inputs. The $O(n)$ case only arises when almost all elements are identical, which is uncommon in real problems.

Complexity analysis

For the distinct-elements versions (both search and find-min), the time complexity is $O(\log n)$. Each iteration eliminates half the remaining elements, and the loop runs at most $\log_2(n)$ times.

For the duplicates versions, the best and average case is still $O(\log n)$, but the worst case is $O(n)$ as explained above.

Space complexity for all variants is $O(1)$, just a few index variables.

Recognizing this pattern

You're probably looking at rotated-sorted-array search when:

• The input is described as a sorted array that has been rotated at some unknown pivot.
• The required complexity is $O(\log n)$, ruling out a linear scan.
• You need to find a target, the minimum, or the pivot itself in a rotated array.
• Duplicates may be present, in which case the worst case degrades to $O(n)$ (you cannot decide which side is sorted when nums[lo] == nums[mid] == nums[hi]).

Common templates:

• Search target, distinct values: at each step, identify the sorted half and check whether the target lies in it. Example: Search in Rotated Sorted Array.
• Search target, duplicates allowed: same idea, but shrink lo/hi by one when the endpoints tie with the midpoint. Example: Search in Rotated Sorted Array II.
• Find the minimum / pivot: compare nums[mid] to nums[hi] to decide which half contains the rotation point. Example: Find Minimum in Rotated Sorted Array.
• Find the minimum with duplicates: same as above but with the nums[mid] == nums[hi] tie-break that costs $O(n)$ worst case. Example: Find Minimum in Rotated Sorted Array II.