Search in Rotated Sorted Array

The problem

Array sorted ascending then rotated at an unknown pivot. All values distinct. Return index of target or -1. Must be O(log n).

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

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

Brute force

Linear scan O(n). Violates the log n requirement once stated.

function searchLinear(nums: number[], target: number): number {
  return nums.indexOf(target);
}

Optimal: binary search with sorted-half test

At mid, at least one side [lo, mid] or [mid, hi] is strictly sorted (distinct values).

1. If nums[mid] === target return mid.
2. If left half sorted (nums[lo] ≤ nums[mid]):
   • if target in [nums[lo], nums[mid]) → hi = mid - 1
   • else → lo = mid + 1
3. Else right half sorted:
   • if target in (nums[mid], nums[hi]] → lo = mid + 1
   • else → hi = mid - 1

function search(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length - 1;

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

    if (nums[lo] <= nums[mid]) {
      // left sorted
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      // right sorted
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

Time	O(log n)
Space	O(1)

Alternative: find pivot then binary search

Two binary searches: min index, then classic search in the correct segment. Same complexity; more code.

Edge cases

• No rotation (already sorted)
• Target is pivot / min element
• Single element
• Target absent

Common bugs

• Using < vs ≤ on nums[lo] <= nums[mid] inconsistently
• Inclusive bounds wrong on target range checks
• Assuming duplicates (LC 81 needs different handling)

Interview delivery

1. Confirm distinct.
2. One of two halves always sorted.
3. Code carefully with inclusive checks.
4. Trace rotated example.
5. Mention duplicates variant.

Related

• Binary Search
• Find Minimum in Rotated Sorted Array
• Time Based Key Value Store
• Two Sum

Identify sorted half carefully

With distinct values, nums[lo] <= nums[mid] means [lo..mid] is sorted (including single-element). Equality happens when lo==mid. If duplicates were allowed, this test breaks and you must shrink lo/hi linearly in the worst case.

Trace [4,5,6,7,0,1,2], target 0

• mid points at 7, left sorted 4..7, target not in [4,7) → go right
• eventually mid hits 0 → return

Two-binary-search approach

1. Find rotation index (min element) with binary search.
2. Binary search target in the correct sorted segment.

Same big-O; more moving parts. Single-pass sorted-half method is tighter.

Further reading

• LeetCode 33 — Search in Rotated Sorted Array
• Binary search