Binary Search
Discarding a half without full sortedness
Binary search needs a reason to throw away a half, and sortedness is only one possible reason.
Key idea
The requirement, restated honestly
Binary search does not require a sorted array. It requires that looking at the middle lets you rule out one side. Sorted arrays give you that, and they are not the only thing that does.
Here is a case with no sortedness at all. A peak is any element greater than both its neighbors, with the ends treated as having imaginary negative infinity beyond them. An arbitrary array can have many peaks, and you must find any one of them.
Why it works
Why a peak can be found in log time
Compare the middle element with its right neighbor. If the middle is smaller, then the values are rising at that point, and following a rising slope must eventually reach a peak before falling off the end. So a peak exists to the right and the left half can go.
If the middle is larger than its right neighbor, the same argument runs leftward: either the middle is itself a peak, or the slope descends and a peak lies at or left of it.
Either way one half is provably peak-free-optional, meaning it can be discarded without losing every answer. That is all binary search ever needs.
Tip
Comparing against a neighbor, not a target
Notice there is no target here. The comparison is between two elements of the array, which is what makes this feel unlike the searches you have written so far.
Whenever a problem gives you an array with local structure but no global order, ask what a single comparison at the middle would let you rule out. If the answer is half, you have a logarithmic solution.
Key idea
Rotated arrays have the same character
A sorted array that has been rotated is not sorted, and it still has enough structure. It consists of two ascending stretches, and every value in the first is larger than every value in the second.
So comparing the middle against one of the endpoints tells you which stretch the middle is in, and that tells you which side the boundary between them lies on. One comparison, half the range gone.
Gotcha
Compare against the right end, not the left
For finding the boundary in a rotated ascending array, comparing the middle with the right end behaves cleanly: greater means the boundary is strictly to the right, otherwise the middle is still a candidate.
Comparing with the left end has an awkward case when the array is not rotated at all, and needs an extra check to avoid getting it backward. Both can be made to work; one needs fewer special cases, and choosing it deliberately is worth a sentence in an interview.
Edge cases
Duplicates break the guarantee
If the array may contain repeated values, a middle equal to the endpoint tells you nothing about which side the boundary is on, and the worst case degrades to O(n).
Most versions of these problems promise distinct values. Check the promise, and if it is absent, say out loud that duplicates cost you the logarithmic guarantee. Noticing that is a stronger signal than producing the code.
Trace the peak search
Run find_peak on [1, 2, 1, 3, 5, 6, 4]. For each pass give mid, the comparison result as rising or falling, and the range afterward as low and high.
This activity type is not wired up yet.
Find Minimum In Rotated Sorted Array
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.