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.
You must write an algorithm with O(log n) runtime complexity.

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.