Search in Rotated Sorted Array — C++ Coding Problem
Difficulty: medium | Category: binary-search
Problem Description
Given a rotated sorted array `nums` (with unique values) and a `target`, return the **index** of `target` if it is in the array, or `-1` otherwise. You must write an algorithm with **O(log n)** runtime complexity. Hint: In each binary search step, one half is always sorted — use that to decide which half to search next.
Examples
Example 1
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Example 2
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
Example 3
Input: nums = [1], target = 0
Output: -1