Overview

A sorted array has been rotated at some unknown pivot. For example, [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2].

Given the rotated array and a target value, return the index of the target if it exists, or -1 if it does not.

Implement searchRotated(nums, target).

Constraints

• All values in nums are unique.
• The array was originally sorted in ascending order, then rotated.
• Must achieve $O(\log n)$ time complexity — a linear scan is not acceptable.
• nums may have length 0.

Examples

searchRotated([4, 5, 6, 7, 0, 1, 2], 0);  // 4
searchRotated([4, 5, 6, 7, 0, 1, 2], 3);  // -1
searchRotated([1], 0);                      // -1
searchRotated([1], 1);                      // 0

Notes

• Modified binary search: at each step, one half of the array is always sorted. Determine which half is sorted and whether the target falls within that sorted range.
• If the target falls in the sorted half, narrow search there; otherwise search the other half.
• Edge cases: single element, target not present, array not rotated at all.

Solution

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

  while (lo <= hi) {
    const mid = (lo + hi) >>> 1;
    if (nums[mid] === target) return mid;

    // Left half is sorted
    if (nums[lo] <= nums[mid]) {
      if (target >= nums[lo] && target < nums[mid]) {
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    // Right half is sorted
    else {
      if (target > nums[mid] && target <= nums[hi]) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
  }

  return -1;
}

Resources

• Search in Rotated Sorted Array — LeetCode
• Binary Search — Wikipedia