Search for a target in a rotated sorted array in O(log n).

How to think about it

Recognise the pattern

A rotated sorted array is still almost sorted — just split at one pivot. The binary search instinct is right: pick a midpoint, but before deciding which half to search, first determine which half is cleanly sorted. That sorted half gives you a reliable range to check the target against.

The signal: sorted (or nearly sorted) input + O(log n) requirement = binary search with an extra comparison.

Build the approach step by step

Brute force: linear scan O(n). Easy but misses the point.

Key insight: cut the array at any midpoint. One of the two halves — left [lo..mid] or right [mid..hi] — must be contiguous and sorted (no rotation crossing through it). You can tell which one by comparing nums[lo] with nums[mid]:

• If nums[lo] <= nums[mid], the left half is sorted.
  • If nums[lo] <= target < nums[mid], search left.
  • Otherwise search right.
• Otherwise the right half is sorted.
  • If nums[mid] < target <= nums[hi], search right.
  • Otherwise search left.

Array: [4, 5, 6, 7, 0, 1, 2], target = 0
lo=0,hi=6,mid=3 -> nums[3]=7, nums[0]=4 <= 7 -> left sorted [4..7]
target=0 not in [4,7) -> search right: lo=4
lo=4,hi=6,mid=5 -> nums[5]=1, nums[4]=0 <= 1 -> left sorted [0..1]
target=0 in [0,1) -> search left: hi=5
lo=4,hi=5,mid=4 -> nums[4]=0 == target -> return 4

Complexity

	Value	Why
Time	O(log n)	Search space still halves each iteration
Space	O(1)	Iterative, no extra memory