LeetCode 33 Search in Rotated Sorted Array - Why Naive Fails

Linear search scans every element until you find the target. That's $O(n)$.

The problem explicitly requires $O(\log n)$ time. You need to apply binary search, but the usual approach breaks because the array isn't fully sorted.

The challenge: how do you decide which half to search when the array wraps around?