Search Rotated Array 25 XP Medium

Search for a target in a rotated sorted array. Return its index or -1 if not found. You must achieve O(log n).

The trick: at any mid point, one half is always sorted. Check if target falls in the sorted half. If yes, search there. Otherwise, search the other half.

• If nums[left] <= nums[mid]: left half is sorted
• Check if target is in [nums[left], nums[mid]]
• Otherwise, right half is sorted — apply similar logic