Search in Rotated Sorted Array

An array sorted in ascending order is rotated at an unknown pivot. Given the array and a target, return the index of the target or -1 if not found. All values are distinct.

Why this is worth learning

Rotation leaves at least one half around the midpoint sorted when values are distinct. Determine which half is ordered before deciding whether the target belongs inside its value range.

Before coding: one-minute experiment

In [4,5,6,7,0,1,2], with midpoint value 7 and target 1, why can the sorted left half be discarded?

Function signature

func Search(nums []int, target int) int

Inputs / outputs

• nums: rotated sorted array with distinct values.
• target: value to search.
• Return: index of target, or -1.

Example

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

Constraints

• 1 <= len(nums) <= 100_000

Core idea (near-solution)

A scan ignores the useful order that survived rotation. With distinct values, the midpoint splits the candidate interval so at least one half is sorted. Recognize that half first, then use its endpoint values to decide whether target can lie there. Comparing target with the midpoint alone is insufficient because the other half may cross the wrap from largest to smallest.

Binary search by identifying which half is sorted. The target must lie in one of the halves.

Invariant: the target (if it exists) is always within the current [lo, hi] range.

Algorithm (step-by-step)

1. Set lo = 0, hi = len(nums)-1.
2. While lo <= hi:
   • mid = lo + (hi-lo)/2.
   • If nums[mid] == target, return mid.
   • If left half is sorted (nums[lo] <= nums[mid]):
     • If nums[lo] <= target < nums[mid], move left (hi = mid-1), else move right.
   • Else right half is sorted:
     • If nums[mid] < target <= nums[hi], move right (lo = mid+1), else move left.
3. Return -1.

Correctness sketch

The inclusive interval contains the target if it exists. After checking midpoint equality, compare nums[lo] with nums[mid]. If the left half is sorted, its closed-open value range [nums[lo],nums[mid]) contains target exactly when the remaining left half could contain it; otherwise discard that half. If the left half crosses the rotation point, the right half is sorted, and the analogous range (nums[mid],nums[hi]] decides whether to keep it. Distinct values make this classification unambiguous. Every update excludes the checked midpoint and strictly reduces the interval without discarding a possible target.

Trace (hand walkthrough)

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

Walk:
- lo=0 hi=6 mid=3 val=7; left sorted [4..7], target 0 not in -> lo=4
- lo=4 hi=6 mid=5 val=1; left sorted [0..1], target 0 in -> hi=4
- mid=4 val=0 -> found index 4

Pitfalls to avoid

• Misplacing the boundary comparisons (<= vs <).
• Forgetting the distinct-values assumption; this logic relies on it.

Debugging lens

Test every pivot, an unrotated input, absent targets between values, and both endpoints. The use of <= when recognizing the sorted left half matters for a one-element half.

Complexity

• Time: O(log n).
• Extra space: O(1).

Implementation notes (Go)

• Use lo + (hi-lo)/2 to avoid overflow.

Reconstruction checkpoint

In [4,5,6,7,0,1,2], with midpoint value 7 and target 1, why can the sorted left half be discarded?

Return to Binary Search · Module quiz