Follow up - search the array many times

• If we only search the array few times, then we can do binary search in O(n) worst case as many have shared.

``````    bool search(vector<int>& nums, int target) {
int l=0,r=nums.size()-1;
while(l<=r) {
int mid = (l+r)/2;
if(nums[mid]==target) return true;
if(nums[mid]<nums[l])
if(target>nums[mid] && target<=nums[r]) l = mid + 1;
else r = mid - 1 ;
else if (nums[mid]>nums[l])
if(target>=nums[l] && target<nums[mid]) r = mid - 1;
else l = mid + 1;
else l++;
}
return false;
}
``````

If we search the array many times, then it is better to find the pivot first in O(n) and then search can be done in O(logn)

``````    int findPivot(vector<int>& nums) {
int l = 0, r = nums.size()-1;
while(l<r) {
int mid = l+(r-l)/2;
if(nums[mid]<nums[r]) r = mid;
else if(nums[mid]>nums[r]) l = mid+1;
else if(nums[r-1]>nums[r]) return r;//if r is pivot
else r--;
}
return l;
}
``````

Note that findPivot is not the same as findMin in rotated sorted array. The difference is the commented line. For example [2,2,4,2], the min could be any of the 2 while the pivot is the last 2 which is the first element in the unrotated form. In rotated sorted array, pivot is the first element that decreases. In findMin, the pivot could be bypassed by r--. This can be avoided by checking if r is the pivot before skipping it. The idea comes from @benlong. Now that we find the pivot, we can search in O(logn) worst case as follows.

``````    bool search(vector<int>& nums, int pivot, int target) {
int l = target <= nums.back()? pivot:0, r = target <= nums.back() ? nums.size()-1:pivot-1;
while(l<=r) {
int mid = l+(r-l)/2;
if(target == nums[mid]) return 1;
if(target<nums[mid]) r = mid-1;
else l = mid+1;
}
return 0;
}
``````

• @yu6 Excellent! Learnt a lot, nice way to find pivot (pivot is not equal to minimum).
-- Stephan Pokemon

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.