Search in Rotated Sorted Array

Try It Yourself

Use the editor below to search a rotated sorted array in logarithmic time. At every step, identify which half is still normally sorted.

Submit your implementation when it passes the examples. Handle one-element arrays, missing values, and targets on either side of the rotation.

Solution

At least one half around the middle is sorted. Determine whether the target lies inside that sorted half; if it does, keep that half, and otherwise search the other side.

This decision preserves binary search's ability to discard half of the remaining array after every comparison.

function searchRotated(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const middle = left + Math.floor((right - left) / 2);
    if (nums[middle] === target) return middle;

    if (nums[left] <= nums[middle]) {
      if (nums[left] <= target && target < nums[middle]) {
        right = middle - 1;
      } else {
        left = middle + 1;
      }
    } else if (nums[middle] < target && target <= nums[right]) {
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }

  return -1;
}

Big O notation