Search in Rotated Sorted Array – Solution & Complexity

• The array was sorted ascending, then rotated at some unknown pivot (e.g. [0,1,2,4,5,6,7] rotated at index 3 becomes [4,5,6,7,0,1,2]).
• You need to find target's index in O(log n) — a plain linear scan is O(n) and defeats the point of the problem.
• Key insight: even though the whole array isn't sorted, at least one of the two halves around any midpoint always is sorted. That's enough to still binary search.

• Keep lo/hi pointers like standard binary search. At each step compute mid.
• Determine which half is sorted by comparing nums[lo] and nums[mid]: if nums[lo] <= nums[mid], the left half [lo..mid] is sorted; otherwise the right half [mid..hi] is sorted.
• Once you know which half is sorted, checking whether target lies within that half's value range is a simple comparison. If it does, search that half; otherwise, search the other half.

• If nums[mid] == target, return mid immediately.
• If left half [lo..mid] is sorted: target is in it exactly when nums[lo] <= target < nums[mid], so narrow hi = mid - 1; otherwise narrow lo = mid + 1.
• If the right half [mid..hi] is sorted instead: target is in it exactly when nums[mid] < target <= nums[hi], so narrow lo = mid + 1; otherwise narrow hi = mid - 1.
• Loop while lo <= hi; if the loop ends without finding target, return -1.

This still runs in O(log n) time and O(1) space — the halving still happens every iteration, just with an extra comparison to figure out which half is sorted.

• Using nums[lo] < nums[mid] instead of <= to detect the sorted half — with only 1-2 elements in a half, lo == mid and the strict inequality misclassifies it as unsorted.
• Off-by-one errors in the range checks (< vs <= at the boundaries) — easy to skip or double-count the boundary element.
• Follow-ups: how does the approach change if the array can contain duplicates (values equal to nums[lo] making it ambiguous which half is sorted — worst case degrades to O(n))? How would you find the rotation pivot index itself?