Search in Rotated Sorted Array

Problem A sorted array of distinct integers was rotated at an unknown pivot. Given the array and a target, return the target's index or -1, in O(log n).

Input / Output

• Input: int array nums (rotated sorted, distinct), int target.
• Output: index of target or -1.

Constraints

• n up to 10^4; O(log n) required — a linear scan is explicitly not accepted.

Example

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