How do you search a rotated sorted array, and what makes the logarithmic version possible?
You use a binary search, but there is one extra step. At each round you work out which half of the remaining range is sorted, and you use that to decide which half to keep.
So what makes the logarithmic version possible? It is that a rotated sorted array still has two sorted pieces, and the middle of the range belongs to one of them. Once you know which piece the middle is in, you know whether the target is on the left or the right, because the sorted piece gives you a real comparison to make.
the range the middle value what you know
-------------------- ---------------- -----------------------
[4, 5, 6, 7, 1, 2, 3] 6 the right half is sorted
[5, 6, 7, 1, 2, 3, 4] 7 the right half is sorted
[6, 7, 1, 2, 3, 4, 5] 2 the left half is sorted
So the answer has three steps. First you check whether the middle value is the target. Then you check whether the left half is sorted, which means the value at the low end is not bigger than the middle value. And then you use those two facts to decide which half to keep.
And there are four cases to think about, and they are the same four every time. The target is in the sorted half, so you check it against the bounds of that half. Or the target is not in the sorted half, so you keep the other half. Or the middle value is the target itself, and you are done.
And the complexity is O of log n for the time, because every round throws half of the range away, just like an ordinary binary search. And O of 1 for the space.
So the rule to remember is this. A rotated array still has one sorted half, and that is all you need to halve the search.
The next two questions in this topic show the code and the simple version.