Search in Rotated Sorted Array

A sorted array of distinct values was rotated at an unknown point (for example 0 1 2 4 5 6 7 → 4 5 6 7 0 1 2). Find the index of target, or -1 if it is not present.

Input:

• line 1: n
• line 2: n distinct integers
• line 3: target

Output: the 0-based index of target, or -1.

Constraints: 1 ≤ n ≤ 10⁵, −10⁴ ≤ a[i], target ≤ 10⁴. Aim for O(log n).

Think about it: at every step, at least one half (lo..mid or mid..hi) is properly sorted. Check whether target lies in that sorted half; if not, it must be in the other.