Search in Rotated Sorted Array
A sorted array was rotated at some unknown pivot (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Given the rotated nums and a target, return its index or -1, still in O(log n).
The insight: at any mid, at least one half is still sorted. Determine which, check whether the target falls inside that sorted half, and discard the other half.
search([4, 5, 6, 7, 0, 1, 2], 0); // 4
search([4, 5, 6, 7, 0, 1, 2], 3); // -1