Description
There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated. 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 = 04The original sorted array [0,1,2,4,5,6,7] was rotated at index 4, placing [4,5,6,7] at the front. Using modified binary search: mid=3 (value 7). Since left portion [4,5,6,7] is sorted and target 0 is not in range [4,7], search right half. New mid=5 (value 1). Right portion [0,1,2] is sorted, target 0 is in range, search left. Found 0 at index 4.
nums = [4,5,6,7,0,1,2], target = 3-1The array contains [4,5,6,7,0,1,2]. Binary search checks mid=3 (value 7), then searches right half [0,1,2] since 3 is not in sorted left [4,7]. Continuing search in [0,1,2], 3 is greater than all values. Since 3 falls between 2 and 4 (the rotation gap), it cannot exist in this array.
nums = [1], target = 0-1With only one element (value 1), the binary search immediately compares target 0 with nums[0]=1. Since 0 != 1, the search space is exhausted and -1 is returned.
Constraints
- •
1 ≤ nums.length ≤ 5000 - •
-10⁴ ≤ nums[i] ≤ 10⁴ - •
All values of nums are unique. - •
nums is an ascending array that is possibly rotated. - •
-10⁴ ≤ target ≤ 10⁴