Prompt
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly left rotated at an unknown 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]] (0-indexed). For example, [0,1,2,4,5,6,7] might be left rotated by 3 indices and become [4,5,6,7,0,1,2].
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.
Solution
In C++
int find_pivot(vector<int>& nums) {
int l = 0; int r = nums.size() - 1;
int n = nums.size();
while (l < r) {
int m = (r - l) / 2 + l;
if (nums[r] < nums[m]) l = m + 1;
else r = m;
}
return l;
}
int bsearch(vector<int>& nums, int target, int pivot) {
int n = nums.size();
int l = 0;
int r = nums.size() - 1;
while (l <= r) {
int m = (r - l) / 2 + l;
int curr = nums[(m + pivot) % n];
if (target > curr) l = m + 1;
else if (target < curr) r = m - 1;
else return (m + pivot) % n;
}
return -1;
}
int search(vector<int>& nums, int target) {
int pivot = find_pivot(nums);
return bsearch(nums, target, pivot);
}Explanation
Basically, we just find the minimum of the array using a modified binary search, and then use the regular binary search algorithm with a modifying index to handle to rotation. The find pivot is a little different because the middle pointer can also have the minimum. The find pivot part is literally 153. Find Minimum in Rotated Sorted Array
Big O Analysis
Time Complexity