Search in Rotated Sorted Array

Problem Given an ascending array that has been rotated at an unknown pivot (no duplicates), search for a target value and return its index, or -1 if absent, in O(log n).

Input / Output

• Input: rotated sorted array nums, integer target.
• Output: index of target, or -1.

Constraints

• 1 ≤ n ≤ 5000; O(log n) required (a linear scan defeats the point).
• The array is a rotation of a strictly ascending array (no duplicates).

Example

• [4,5,6,7,0,1,2], target = 0 → 4.
• target = 3 → -1.