Search in Rotated Sorted Array

A sorted array 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 if not present, in O(log n).

Example

Input: nums = 4 5 6 7 0 1 2, target = 0 Output: 4

Approach

Modified binary search: at each step, at least one half (low..mid or mid..high) is guaranteed to be normally sorted. Determine which half is sorted, then check whether the target lies within that half's range to decide which side to continue into.

Input format

Line 1: the array, space-separated Line 2: target