Medium
Binary Search
Search in Rotated Sorted Array
At every step, one half is still sorted — decide which, then whether the target lies in it.
Approach
Binary search as usual, but first determine which side of mid is sorted (compare nums[lo] to nums[mid]). If the target falls within that sorted side's range, search there; otherwise search the other half. The rotation never breaks the halving.
Time complexity
O(log n)
Space complexity
O(1)
Common mistake
Assuming the whole array is monotonic — you must check which half is sorted before choosing a direction.
See it run, step by step
Generate an interactive lesson for Search in Rotated Sorted Array — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Search in Rotated Sorted Array