33. Search in Rotated Sorted Array

A sorted array of distinct values was rotated at an unknown pivot. Return the index of target, or -1 if it is absent, in O(log n) time.

At every mid, at least one half is sorted. If target lies inside the sorted half's range, search there; otherwise search the other half.

1function search(nums: number[], target: number): number {
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]) {
7      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
8      else lo = mid + 1;
9    } else {
10      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
11      else hi = mid - 1;
12    }
13  }
14  return -1;
15}

target = 0lo = 0hi = 6

nums

Search the whole array.

1 / 0

Space: play/pause · ←/→: step