Search in Rotated Sorted Array
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with **O(log n)** runtime complexity.
Examples
nums = [4,5,6,7,0,1,2], target = 04nums = [4,5,6,7,0,1,2], target = 3-1nums = [1], target = 0-1Constraints
1 <= nums.length <= 5000-10^4 <= nums[i] <= 10^4All values of nums are uniquenums is an ascending array that is possibly rotated
š” Hints
Hint 1
At any point, one half of the array is always sorted.
Hint 2
Check if the target lies in the sorted half. If yes, search there. Otherwise, search the other half.
Hint 3
Use standard binary search with an extra conditional to determine which half is sorted.
Algorithm Complexity
Official asymptotic Big-O runtime and auxiliary memory analysis
Modified binary search. At each step, determine which half is sorted. If the target is in the sorted range, search there. Otherwise, search the other half.
Determines which half of the array is normally sorted and discards half the search space at each comparison.
Operates in-place with constant auxiliary pointers (left, right, mid).
š Real-World Use Cases
Searching for a value in a circular log buffer where entries wrap around ā the same rotated binary search logic applies.
š Dry Run
Search for 0 in [4,5,6,7,0,1,2]. Initialize left=0, right=6.