4.11.5 — Search in Rotated Sorted Array

LeetCode 33 · Medium · ★ Blind 75

The problem

A sorted array of distinct values has been rotated. Find target and return its index, or −1. Must be O(\log n).

nums = [4,5,6,7,0,1,2], target = 0   →  4
nums = [4,5,6,7,0,1,2], target = 3   →  -1

The pattern

Same array shape as 4.11.4 — two sorted runs with one drop between them. Now you want an arbitrary value rather than the minimum.

The problem with ordinary binary search here is that nums[mid] < target no longer tells you which way to go, because the array is not globally sorted.

Here is the fix, and it is the whole idea:

Cut at mid, and one of the two halves is always a clean, unbroken sorted run. The drop can only be in one of them.

So at every step:

1. Work out which half is the clean one.
2. Check whether the target lies inside that half's range. Because it is sorted, that is a simple two-sided comparison.
3. If yes, search there. If no, search the other half.

Either way you discard half the array, so it is still O(\log n).

[4, 5, 6, 7, 0, 1, 2]
 └────┬────┘
   mid = 7

left half [4,5,6,7] is clean and sorted
right half [0,1,2] contains the drop... actually no:
the drop is between 7 and 0, at the boundary.
The rule below settles it precisely.

Deciding which half is clean

Compare nums[low] with nums[mid].

• If nums[low] <= nums[mid], the left half rises with no break, so the left half is clean.
• Otherwise the drop is somewhere in the left half, so the right half is clean.

The <= matters: when low == mid, which happens on a one-element range, the comparison must count that single element as sorted.

The solution

Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1

        while low <= high:
            mid = low + (high - low) // 2

            if nums[mid] == target:
                return mid

            if nums[low] <= nums[mid]:                 # left half is clean
                if nums[low] <= target < nums[mid]:    # target is inside it
                    high = mid - 1
                else:
                    low = mid + 1
            else:                                      # right half is clean
                if nums[mid] < target <= nums[high]:   # target is inside it
                    low = mid + 1
                else:
                    high = mid - 1

        return -1

TypeScript

function search(nums: number[], target: number): number {
  let low = 0, high = nums.length - 1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);

    if (nums[mid] === target) return mid;

    if (nums[low] <= nums[mid]) {
      if (nums[low] <= target && target < nums[mid]) high = mid - 1;
      else low = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[high]) low = mid + 1;
      else high = mid - 1;
    }
  }

  return -1;
}

This is shape A — an exact-element search — so high = len - 1 and the loop is while low <= high.

The range checks are deliberately asymmetric. On the clean left half the test is nums[low] <= target < nums[mid], with mid excluded because it was already checked and rejected. On the clean right half it is nums[mid] < target <= nums[high], again excluding mid. Getting an inclusive bound wrong here causes an infinite loop or a missed answer, so read them once carefully.

The else branches carry the real weight. If the target is not in the clean half, then it is either in the messy half or nowhere. Searching the messy half is safe because the next iteration will split it again and one of its halves will be clean. The recursion of the argument is what makes one pass enough.

Trace

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

low	high	mid	nums[mid]	clean half	target in it?	action
0	6	3	7	left [4..7] (4 ≤ 7)	0 is not in [4,7)	low = 4
4	6	5	1	left [0..1] (0 ≤ 1)	0 is in [0,1)	high = 4
4	4	4	0	—	found	return 4

Complexity

O(\log n) time, O(1) space.

The two-pass alternative

Simpler to get right, and worth offering:

1. Find the rotation point with the code from 4.11.4. That is O(\log n).
2. Decide which of the two runs could contain the target, by comparing against the ends.
3. Run an ordinary binary search on that run.

Same complexity, two easy pieces instead of one tricky one. If the four-branch version is going wrong under pressure, switch to this. Two correct binary searches beat one confused one.

There is a third trick worth knowing: binary search over the whole array as if it were sorted, but map each index through the rotation offset before reading it. It is elegant and fiddly, and it is not the answer to give first.

Duplicates

Search in Rotated Sorted Array II (LeetCode 81) allows repeats. When nums[low] == nums[mid] you can no longer tell which half is clean — [3,1,3,3,3] and [3,3,3,1,3] look identical at that comparison.

The fallback is low += 1, discarding one duplicate. The worst case becomes O(n), and as in 4.11.4 that degradation cannot be avoided.

What the interviewer will push on

"Why is one half always sorted?" There is exactly one drop, so it can only fall in one half; the other is unbroken.

"How do you decide which half is clean?" nums[low] <= nums[mid], and the <= handles the one-element case.

"Why are your range checks half-open?" mid was already tested and rejected, so it must be excluded from both.

"Can you do it in two passes instead?" Yes — find the pivot, then search the right run. Same complexity, easier to write.

"What if there are duplicates?" low += 1 on ties, and the worst case becomes linear.

One thing to volunteer: say the invariant before writing code. "One half is always cleanly sorted, so I check whether the target lies in that half's range; if not, I search the other half." This problem is entirely that sentence.

Next: 4.11.6 Time Based Key-Value Store — binary search inside a design problem, looking for the largest value not exceeding a target.