Search in Rotated Sorted Array
A sorted array of distinct numbers was rotated. Return the index of target, or -1 if it isn't there, in O(log n).
A way to picture it
Cut a sorted deck of cards anywhere and look at the middle card. At least one side of it is still in perfect order. If your card belongs inside that orderly side, search there; otherwise it's on the messy side.
How to approach it
At every step one half is sorted. Check whether the target falls inside the sorted half's range, and throw away the other half.
Example
Input: {"nums":[4,5,6,7,0,1,2],"target":0}. Output: 4.
Complexity: O(log n) time and O(1) space. Each step discards half the range.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.