Follow up - search the array many times


  • 1

    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;
        }
    

  • 1
    W

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


Log in to reply
 

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