Search in Rotated Sorted Array

Problem

Take an ascending array of distinct integers and cut it at some position you are not told, then swap the two pieces: [2, 3, 6, 12, 15, 18] cut before the 15 becomes [15, 18, 2, 3, 6, 12]. Given the rotated array nums and an integer target, return the index of target in nums, or -1 if it is absent. The solution should take logarithmic time.

• nums has between 1 and 8,000 elements, all distinct.
• Values and target are integers between -1,000,000 and 1,000,000.
• The cut may be at position zero, in which case the array is simply sorted.

Examples

• nums = [15, 18, 2, 3, 6, 12], target = 6 → 4.
• nums = [15, 18, 2, 3, 6, 12], target = 10 → -1; 10 would sit between 6 and 12 in the sorted order, and nothing is there.
• nums = [7, 3], target = 3 → 1. Tiny inputs are where the half-selection logic usually breaks.

Hints

1. Plain binary search fails because comparing target to nums[mid] no longer tells you which side to go. What extra comparison would restore that information?
2. Split the array at mid. Can both halves be "broken" by the rotation at the same time?
3. Exactly one half is sorted. Check whether target lies inside that sorted half's value range; if yes go there, otherwise go to the other half.