Q33: Search in Rotated Sorted Array

Given a rotated sorted array and a target integer, return its index or -1 if not found in $O(\log n)$ time using modified Binary Search.

Rotated Sorted Array Search

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

console.log(search([4,5,6,7,0,1,2], 0)); // 4

💡 Identifies which half is sorted. If target lies within bounds of the sorted half, moves search space into that range; otherwise shifts into opposite partition.

Key Takeaways

At least one partition half (left..mid or mid..right) is guaranteed to be sorted at any binary search step.
Check if target falls within sorted half boundaries to decide search direction.

Knowledge Check

What structural guarantee enables binary search on a rotated sorted array?

Q33: Search in Rotated Sorted Array

STAY UPDATED WITH BYTES!