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.

Expected approach

• Modified binary search: at each step one half is guaranteed sorted (compare nums[lo] vs nums[mid]). If the target lies inside the sorted half's range, recurse there; otherwise recurse into the other half. O(log n) time, O(1) space. Follow-on variants worth knowing: duplicates allowed (worst case degrades to O(n)), find-minimum / find-pivot in a rotated array.