Binary Search
Working out which half is trustworthy
When one half is reliably sorted and the other is not, you can still decide where to go.
Why it works
The structural fact
Split a rotated ascending array anywhere. The rotation point falls in one of the two halves, so the other half contains no rotation point and is therefore plainly sorted.
You can tell which by one comparison: if the leftmost element of a half is not greater than its rightmost, that half is sorted.
Key idea
What a sorted half buys you
For a sorted half, deciding whether a target is inside it is a single range test: is the target at or above the left end and at or below the right end?
If it is, search that half. If it is not, the target can only be in the messy half, so search that one instead. Either way you discard half, and the messy half becomes the new problem, which has the same structure.
That is the whole algorithm: identify the trustworthy half, use it to make a decision, recurse on whichever half survives.
Gotcha
Include mid in exactly one half
Whichever half you test, mid must belong to one of them and only one. Testing the left half as low through mid and the right half as mid through high puts mid in both, which makes the two range tests overlap and can send the search in a direction that discards the answer.
Pick a convention such as left is low through mid and right is mid + 1 through high, and keep it consistent through every comparison in the function.
Edge cases
The range test uses closed comparisons
The target might be exactly the endpoint of the sorted half, so the range test needs to include both ends. Using strict comparisons drops answers that sit exactly on a boundary, and those are precisely the cases small hand-written tests tend to include.
Test with the target at the first position, at the last position, at the rotation point, and absent entirely. Those four cover almost every way this goes wrong.
Tip
An unrotated array is a special case, not a separate case
If the array was rotated by zero, the whole thing is sorted, the left half test succeeds immediately, and the algorithm reduces to ordinary binary search. No extra branch is needed.
Code that special-cases the unrotated array usually has a bug somewhere else, because a correct general version already handles it. When you find yourself adding a special case, check first whether the general logic already covers it.
Find the branch that will not shrink
This finds the smallest value in a rotated sorted array, which is the problem you just solved. It hangs on some inputs. Click the line responsible.
This activity type is not wired up yet.
Search 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.