LeetCode 33 · Binary Search · Arrays

Search in Rotated Sorted Array

MediumBinary search a rotated array — one half is always still sorted.
An ascending sorted array was rotated at some unknown pivot (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Given the array and a target, return the index of the target, or −1. The algorithm must run in O(log n).

Walkthrough

try:
A sorted array rotated at some pivot. Each step, one half of [lo, hi] is still sorted — use it to decide which half to keep.
0
1
2
3
4
5
6
4
5
6
7
0
1
2
lo
·
·
·
·
·
hi
target0
midsorted halfdiscardedfound
1
function search(nums, target) {
2
  let lo = 0, hi = nums.length - 1;
◄
3
  while (lo <= hi) {
4
    const mid = (lo + hi) >> 1;
5
    if (nums[mid] === target) return mid;
6
    if (nums[lo] <= nums[mid]) {          // left sorted
7
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
8
      else lo = mid + 1;
9
    } else {                              // right sorted
10
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
11
      else hi = mid - 1;
12
    }
13
  }
14
  return -1;
15
}
lo = 0hi = 6target = 0
step 0 / 8
line 2
Search window [0, 6]
Binary search still works on a rotated array — one half is always properly sorted. Look for target = 0.

Intuition

Plain binary search breaks because the array isn’t globally sorted. But here is the key observation: no matter where you cut, at least ONE half of [lo, hi] is still perfectly sorted.

Compare nums[lo] with nums[mid]: if nums[lo] ≤ nums[mid], the left half is the sorted one; otherwise the rotation lies on the left and the right half is sorted.

Inside the sorted half you can test the target with a simple range check — that half is ordinary sorted data.

If the target falls inside the sorted half, search there; otherwise it must be in the other half. Either way you throw away half the array each step → O(log n).

The algorithm

  1. 01Set lo = 0, hi = n − 1.
  2. 02Take mid; if nums[mid] is the target, return mid.
  3. 03Decide which half is sorted by comparing nums[lo] and nums[mid].
  4. 04If the target lies inside that sorted half’s range, keep it; otherwise keep the other half.
  5. 05Repeat until lo > hi, then return −1.

Reference implementation

1
function search(nums, target) {
2
  let lo = 0, hi = nums.length - 1;
3
  while (lo <= hi) {
4
    const mid = (lo + hi) >> 1;
5
    if (nums[mid] === target) return mid;
6
    if (nums[lo] <= nums[mid]) {               // left half sorted
7
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
8
      else lo = mid + 1;
9
    } else {                                   // right half sorted
10
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
11
      else hi = mid - 1;
12
    }
13
  }
14
  return -1;
15
}

Complexity

Time
O(log n) — the window halves each iteration.
Space
O(1).