Search for a target in a rotated sorted array. The array was sorted then rotated at an unknown pivot. Must be O(log n).

Example 1:

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

Example 2:

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

Constraints:

• 1 ≤ nums.length ≤ 5000
• All values are unique.

Extends binary search to handle rotated sorted arrays. Tests deep understanding of the binary search invariant.

Pattern: Modified Binary Search

Even in a rotated array, at least one half is fully sorted. Determine which half, then check if target lies in it.

graph TD
    Start["Input Data"] --> Process["Process Element by Element"]
    Process --> Lookup{"Hash Map / Set Lookup"}
    Lookup -- "Match Found" --> Return["Return Indices / Result"]
    Lookup -- "No Match" --> Store["Store in Map / Set"]
    Store --> Process

function search(nums, target) { return nums.indexOf(target); }

• Time Complexity: O(n)
• Space Complexity: O(1)
• Explanation: Linear scan via indexOf.

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

• Time Complexity: O(log n)
• Space Complexity: O(1)
• Explanation: Modified binary search identifying sorted halves.

1. Initialize State: Setup necessary pointers, dynamic programming arrays, or hash maps.
2. Iterate & Evaluate: Process the input according to the boundary conditions.
3. Update & Return: Compute the optimal answer and return early or at termination.

1. Check which half is sorted via nums[left] <= nums[mid]
2. If target is in sorted half, search there
3. Otherwise search the other half

1. One half is always sorted.
2. Compare nums[left] with nums[mid] to determine which half.
3. Check if target falls in the sorted half.

👉 Solve this problem interactively in the DSA Lab