Medium · Modified Binary Search
Understand → Visualise → Practice.
Distinct ascending values were rotated once. Return the target index or −1.
In a rotated sorted array, at least one of the two halves around mid is in order. Check whether the target lies in that sorted half; if not, search the other.
If nums[mid] is the target, return mid.
If nums[lo] ≤ nums[mid], the left half is sorted; otherwise the right half is.
If the target is within the sorted half's range, search there; otherwise search the other half.
O(log n) time and O(1) space.
Using strict < when testing whether the left half is sorted breaks when lo == mid.
Read the full guides first: Sorting Algorithms and Their Trade-offs, Binary Search and Boundary Finding.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.