Description:
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand, for example, [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2].
You are given a target value to search. If found in the array, return its index; otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
Example:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1Input: nums = [1], target = 0
Output: -1This problem asks you to search for a target in a sorted array that has been rotated at an unknown pivot and return its index, or -1 if it does not exist. The key is to use binary search while identifying which half of the array remains sorted at each step, then narrow the search to the side that can contain the target. Because duplicates are not allowed, the logic stays clean and the solution runs in O(log n) time.
