LeetCode 33 · Medium · Binary Search

Search in Rotated Sorted Array

A sorted array of distinct integers may have been rotated, so it starts somewhere in the middle of its sorted order. Return the index of target, or -1 if it is missing, in O(log n) time.

O(log n)time
O(1)space
1 half sortedtest the target against it

nums: 1–16 distinct integers, −99 to 99, a sorted list rotated any number of times · target: −999 to 999

public int search(int[] nums, int target) { int l = 0; int r = nums.length - 1; while (l <= r) { int m = l + (r - l) / 2; if (nums[m] == target) { return m; } if (nums[l] <= nums[m]) { // l..m is sorted if (target < nums[l] || target > nums[m]) { l = m + 1; } else { r = m - 1; } } else { // m..r is sorted if (target < nums[m] || target > nums[r]) { r = m - 1; } else { l = m + 1; } } } return -1;}
l
—
r
—
m
—
nums[m]
—
sorted half
—

Why it works

  1. Brute force scans every value: O(n). Another route finds the rotation point first (153) and then runs a plain binary search on the correct piece: still O(log n), but two passes.
  2. Key insight: one half is always sorted. Cut [l, r] at m and at most one side contains the drop. Compare nums[l] with nums[m] to see which side is clean. A sorted run has known bounds, so one range check says whether target can be inside it. If yes, keep it; if no, keep the other side.
  3. O(log n) time, O(1) space. Every probe discards half of [l, r], exactly as in plain binary search; only the rule for picking the half changed.
  4. Pitfall: <= in nums[l] <= nums[m]. When l == m (two cells left) the left "half" is the single cell m, which is sorted. With <, [3, 1] and target 1 picks the wrong side and returns -1.
  5. Follow-up: with duplicates (81), nums[l] == nums[m] hides which side is sorted. Step l forward by one and retry; the worst case becomes O(n).