A rotated sorted array is an array that was originally sorted but then shifted some number of times (e.g., [4, 5, 6, 7, 0, 1, 2] was [0, 1, 2, 4, 5, 6, 7] rotated 4 times).

Think of a Circular Staircase:

1. Usually, stairs only go up.
2. In a rotated array, the stairs go "Up, Up, Up" then suddenly Drop back to the bottom, then "Up, Up" again.
3. If you stand on any step and look at the middle of the staircase:
   • Either the part to your left is a normal, straight staircase (Sorted).
   • Or the part to your right is a normal, straight staircase (Sorted).
4. You can still use Binary Search, you just need to check which side is "normal" before deciding where to jump.

---

The Core Strategy

When you pick a mid element in a rotated array, at least one half (left to mid or mid to right) must be sorted.

1. Check if the left half [low...mid] is sorted.
2. If yes, check if the target lies within that range.
3. If not, the right half [mid...high] must be sorted. Check if the target is there.

Complexity Analysis

• Time: $O(\log n)$. It's still a Binary Search, just with more conditions.
• Space: $O(1)$.

---

javascript Standard
/**
 * Find index of target in rotated sorted array.
 */
function search(nums, target) {
  let low = 0;
  let high = nums.length - 1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);

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

    // Identify which half is sorted
    if (nums[low] <= nums[mid]) {
      // Left side is sorted
      if (nums[low] <= target && target < nums[mid]) {
        high = mid - 1; // Target is in the sorted left half
      } else {
        low = mid + 1;  // Target must be in the right half
      }
    } else {
      // Right side must be sorted
      if (nums[mid] < target && target <= nums[high]) {
        low = mid + 1; // Target is in the sorted right half
      } else {
        high = mid - 1; // Target must be in the left half
      }
    }
  }

  return -1;
}

---

Variations

• Find Minimum in Rotated Sorted Array: Use binary search to find the "pivot" point where the drop happens.
• Search in Rotated Sorted Array II: What if there are duplicates? (e.g., [2, 5, 6, 0, 0, 1, 2]). This becomes $O(n)$ in the worst case!

Crucial Note

Whenever you see "Sorted Array" + "Find something", always think Binary Search first. If it's shifted or rotated, the logic doesn't change, just the conditions. Blackwell