Search in Rotated Sorted Array

Statement

You are given an integer array nums sorted in ascending order with distinct values, then rotated at some unknown pivot index k. Given a target value, return its index, or −1 if not present. Solve in O(log n).

Examples

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

Constraints

• 1 ≤ len(nums) ≤ 5000
• -10⁴ ≤ nums[i] ≤ 10⁴
• All values in nums are unique (no duplicates).
• Solve in O(log n).

What this problem is really testing

Whether you can adapt binary search to a piecewise-monotone array. The trick: even though the array isn't fully sorted, at each midpoint at least one half is sorted. Identifying which half is sorted, then deciding whether the target lies in it, drives the next iteration. This is binary search with one extra inspection per step. O(log n) preserved.