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

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

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