Search in Rotated Sorted Array

A sorted array (e.g., [0, 1, 2, 4, 5, 6, 7]) is rotated at some pivot.

• Example Rotation: [4, 5, 6, 7, 0, 1, 2].

Given this rotated array and a target target, return the index of target. If not found, return -1.
The search has to run in O(log n) time, so a straight scan through the array is not enough.

Examples

• ([4,5,6,7,0,1,2]), target = 0 -> Index 4.
• ([4,5,6,7,0,1,2]), target = 3 -> -1.

Simply iterate through the array and look for the target.

for(let i=0; i<nums.length; i++) {
    if (nums[i] === target) return i;
}
return -1;

Complexity: O(n).
This is trivial but violates the O(log n) requirement.

Even though the array is rotated, at any split (midpoint), at least one half must be sorted.

Consider [4, 5, 6, 7, 0, 1, 2]:

1. Mid at index 3 (Value 7).
   • Left part [4, 5, 6, 7] is sorted (4 <= 7).
   • Right part [7, 0, 1, 2] is NOT sorted.

We can use this property:

1. Identify which half is sorted.
2. Check if the target lies within that sorted half's range.
3. If yes, search that half.
4. If no, search the other half.

Observe how the algorithm decides which half to search based on the sorted property.