Search in rotated sorted array

Medium TimeO(log n) SpaceO(1)

A sorted array has been rotated at an unknown point, so [0, 1, 2, 4, 5, 6, 7] might arrive as [4, 5, 6, 7, 0, 1, 2]. Given one of these as nums and a target, return the target's index, or -1 when it is absent. The values are distinct, the rotation point is not given, and an array rotated by nothing is simply sorted and must still work.

Examples

Example 1

Input
nums = [4, 5, 6, 7, 0, 1, 2]target = 0
Output
4
The rotation moved 0 off the front; it now sits at index 4.

Example 2

Input
nums = [0, 1, 2, 4, 5, 6, 7]target = 7
Output
6
Rotated by nothing, so it is plainly sorted and 7 is last, at index 6.

The Code

function search(nums, target) {
  let lo = 0;
  let hi = nums.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}
search([4, 5, 6, 7, 0, 1, 2], 0);
Done
Step through search([4, 5, 6, 7, 0, 1, 2], 0) call by call

More like this

All searching examples (8) →