12. Search in Rotated Sorted Array

Difficulty:MediumPattern:Modified Binary SearchTime:O(log n)Space:O(1)

Given a rotated sorted array nums and a target, return the index of target if it is in nums, or -1 if it is not, in $O(\log n)$ time.

How It Works & Algorithmic Design

Solves using Modified Binary Search:

Compute mid = left + (right - left) / 2.
Identify Sorted Half: Check if nums[left] <= nums[mid]:
- Left Half Sorted: If nums[left] <= target < nums[mid], search left (right = mid - 1); else search right (left = mid + 1).
- Right Half Sorted: If nums[mid] < target <= nums[right], search right (left = mid + 1); else search left (right = mid - 1).
Repeat until left > right or target found.

Why This Approach Works Best

At least one half of a rotated sorted array remains strictly sorted at any given mid point, preserving $O(\log n)$ search efficiency.

Example Walkthrough

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

Rotated sorted array.

Step 1: left=0, right=6, mid=3 (nums[3]=7). Left half [4..7] sorted. 0 not in [4..7] -> left=4.

Searches right partition.

Step 2: left=4, right=6, mid=4 (nums[4]=0). Match!

Found at index 4.

Output: 4

Index of target 0.

Answer: Binary search in rotated sorted array

function search(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) return mid;
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return -1;
}

💡 Determine which half is sorted to prune search space logarithmically.

Key Takeaways

At least one side of the pivot is always sorted.
Checking range bounds decides which side to eliminate.
Achieves optimal $O(\log n)$ runtime.