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

To put this in plain English: you have an array that was originally sorted, but a piece of it was moved from the back to the front. You need to find the exact index of a given target number, but you must do it faster than checking every single element.

Constraints to Keep in Mind:

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values in nums are unique.
• nums is an ascending array that is possibly rotated.
• -10^4 <= target <= 10^4

The Brute Force Approach

The simplest approach is a linear scan.

• How it works: You iterate through nums using a for loop, checking if nums[i] == target. If you find it, return i. If the loop finishes without finding it, return -1.
• Why it's too slow: A linear scan visits every element once, giving an O(n) time complexity. The problem explicitly requires O(\log n) time, forcing us to use binary search. Since the array isn't fully sorted, we can't use standard binary search directly.

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;
}

Code Walkthrough

1. low, high = 0, len(nums) - 1: Standard binary search pointers.
2. while low <= high:: We use <= because we are looking for a specific target element that could be exactly at low == high.
3. mid = low + (high - low) // 2: Pick the middle index safely.
4. if nums[mid] == target:: Immediate win. Return mid.
5. if nums[low] <= nums[mid]:: This checks if the left half [low...mid] is strictly ascending (clean).
   • If clean, we check if our target lies within [nums[low], nums[mid]). If yes, the target MUST be in this left half, so we search it: high = mid - 1. If not, we search the right half: low = mid + 1.
6. else:: If the left half isn't clean, the right half [mid...high] MUST be clean.
   • We check if our target lies within (nums[mid], nums[high]]. If yes, the target MUST be in this right half, so we search it: low = mid + 1. If not, we search the left half: high = mid - 1.
7. If the loop ends, the target wasn't found, 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

• Time Complexity: O(\log n). Even though the array is rotated, we always safely discard at least half of the remaining elements at each step. By the master theorem (or just logic), halving n repeatedly gives \log_2 n operations.
• Space Complexity: O(1). We are only storing pointers (low, high, mid), which take a constant amount of extra memory.

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.