Search in Rotated Sorted Array

Difficulty: Medium

Imagine a list of distinct numbers sorted from smallest to largest, and then someone chops off the front chunk and moves it to the back — for example [0, 1, 2, 4, 5, 6, 7] becoming [4, 5, 6, 7, 0, 1, 2]. That's a "rotated" sorted list: it's still built out of a sorted list, it just no longer starts at the smallest value.

You're given a list that's been rotated this way, along with a target number. Find the index of the target, or report that it isn't there.

Examples

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4

0 sits at index 4.

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1

3 never appears anywhere in this particular rotated list.

Input: nums = [1], target = 0
Output: -1

The list has one element and it isn't the target.

Constraints

  • 1 <= nums.length <= 5000

  • -10^4 <= nums[i] <= 10^4

  • All values of nums are unique.

  • nums is an ascending list that has been rotated at some unknown pivot.

  • -10^4 <= target <= 10^4

Approach

Scanning every element still finds the target, but it throws away the fact that the list is still made of two sorted pieces — it's just that one piece got moved to the end.

At any point during a binary search on this list, look at the middle element. One of the two halves (from the left boundary to the middle, or from the middle to the right boundary) is always a normal, fully sorted run, and you can tell which one just by comparing its two endpoints. Once you know which half is sorted, checking whether the target falls inside that half's value range is a plain comparison. If it does, search that half; if it doesn't, the target must be in the other half, so search there instead. Either way, half the list is thrown away each round, exactly like ordinary binary search.

Solutions

Brute Force — Linear Scan

Check every element until the target turns up. The rotation doesn't matter at all here — a full scan finds it, just slowly.

function search(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) return i;
  }
  return -1;
}

Time: O(n) · Space: O(1)

Optimal — Modified Binary Search

Run a binary search, but at each step first figure out which half of the current range is a normal sorted run, then use that half's value range to decide whether the target could be in it.

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

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] === target) return mid;

    if (nums[left] <= nums[mid]) {
      // Left half is a normal sorted run.
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // Right half is a normal sorted run.
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

Time: O(log n) · Space: O(1)