Binary search that figures out which half is sorted at each step to handle a rotated array.
A rotated sorted array is a sorted array that has been "rotated" at some pivot point. For example, [4,5,6,7,0,1,2] is [0,1,2,4,5,6,7] rotated at index 3. Binary search still works in O(log n): at each step, determine which half is fully sorted, then check whether the target falls inside that sorted half. If yes, narrow to that half; otherwise narrow to the other half.
At each iteration, compute mid. If arr[lo] ≤ arr[mid], the left half [lo..mid] is fully sorted (no rotation break inside). Otherwise the right half [mid..hi] is fully sorted. This check is the key insight that makes binary search possible on a rotated array.
Once you know which half is sorted, check whether the target falls within its bounds. If the left half is sorted and arr[lo] ≤ target < arr[mid], search left (hi = mid − 1). Otherwise search right (lo = mid + 1). Apply the mirror logic for a sorted right half.
Each iteration halves the search space, so the total number of iterations is O(log n). No extra data structures are needed beyond a few pointer variables.
This technique generalises to "Search in Rotated Array II" (with duplicates) and "Find Minimum in Rotated Sorted Array". The core trick (identify the sorted half, then decide which side to narrow) applies to any problem where one half is guaranteed to be monotone.