Java solution. O(N) only if nums[i]==const (avoids full scan if nums[mid]==nums[end])


  • 0
    G

    We do ordinary binary search.

    begin . . . mid . . . end

    There's the rub if our interval nums[mid]==nums[end]. In this case nums[i]==nums[end] on one of the subintervals at least. And binary search would be O(N). We should find mid such as nums[mid]!=nums[end]. We know that all elements, which are not equal to nums[end], must be grouped together. If the quantity of this elements more then (end-begin)/2, we should try m=begin+(end-begin)/2 and we will reliably find mid. If the quantity of this elements more then (end-begin)/4, we should try m=begin+k*(end-begin)/4 and so on.

        public boolean search(int[] nums, int target) {
            int b=0, e=nums.length-1; 
            if(e<0)
                return false;
            if(nums[e]==target || nums[b]==target)
                return true;
            while(b<e){ 
                // try to find m: b < m < e, nums[m]!=nums[e]
                // d - initial step  
                // 0...d.6 - if d==2**n, we can half d on every iteration without skipping any elements
                int d = Integer.highestOneBit(e-b);
                int m=b;
                while(d>0){
                    // We must check every dth element. But we have already checked the even elements. Thus we check only m=b+d*(2*k+1)
                    for(m=b+d; m<e && nums[m]==nums[e]; m+=(d<<1));
                    // we have found m
                    if(m<e)
                        break;
                    // shrink the step
                    d>>>=1;
                }
                // could not find m
                if(d==0)
                    return false;
                // new limits 
                b = m - d;
                if(m+d < e)
                    e = m+d;
                // binary search
                if(nums[m]==target)
                    return true;
                else if( //right
                    nums[e]<nums[m] && nums[m]<target ||
                    nums[e]>target  && nums[m]<target ||
                    nums[e]>target  && nums[e]<nums[m]
                ){
                    if(b==m)
                        return false;
                    b=m;
                }
                else if( //left
                    nums[e]>nums[m] && nums[m]>target ||
                    nums[e]<target  && nums[m]>target ||
                    nums[e]<target  && nums[e]>nums[m]
                ){
                    e=m;
                }
            }
            return false;
        }
    

Log in to reply
 

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