Search in Rotated Sorted Array

Problem

A sorted array (distinct values) has been rotated at an unknown pivot (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Given the rotated array and a target, return its index, or −1. Required: O(log n).

Examples

Constraints

1 ≤ n ≤ 5000 · distinct values · rotated at some unknown pivot (possibly 0, i.e. not rotated at all).

Attempt it first

The array as a whole isn't sorted, so the plain invariant template doesn't directly apply — but a crucial fact rescues it: at least one half of any split is always fully sorted. Find that fact yourself by sketching a few rotated examples and splitting them at the midpoint before opening the hint.