Search in Rotated Sorted Array

Binary search is a powerful algorithm that finds elements in sorted arrays by repeatedly dividing the search space in half. The key insight is that we can eliminate half the possibilities with each comparison, achieving O(log n) time complexity.

In a standard sorted array, binary search works by comparing the target with the middle element. If the target is smaller, we search the left half; if larger, we search the right half. But what happens when the sorted array has been rotated?

A rotated sorted array maintains its sorted property in two separate segments. For example, [1,2,3,4,5,6,7] rotated becomes [4,5,6,7,1,2,3]. Notice that [4,5,6,7] is sorted and [1,2,3] is sorted, but the rotation point creates a "break" where a large number is followed by a smaller one.

The brilliant insight for searching rotated arrays is that at least one half of the array is always properly sorted. When we pick a middle point, we can determine which half maintains the sorted property by comparing the middle element with the boundary elements.

Once we identify the sorted half, we can use normal binary search logic: check if our target falls within the range of the sorted half. If it does, search that half. If not, the target must be in the other half (which might contain the rotation point).

This approach maintains the O(log n) time complexity because we still eliminate half the search space with each iteration, just like regular binary search. The only difference is our decision-making process for choosing which half to explore.