# Still O(logN) doesn't have to degenerate to O(N) solution

• ``````public class Solution {
public int findMin(int[] num) {
if(num==null || num.length==0) return 0;
return helper(num,0,num.length-1);
}

public int helper(int[]num, int start, int end){
if(num[start]<num[end]) return num[start];
while(start+1<end){
int mid = start + (end-start)/2;
if(mid>0 && num[mid]<num[mid-1]){
return num[mid];
}else if(num[mid]>num[0]){
start = mid+1;
}else if(num[mid]<num[num.length-1]){
end = mid-1;
}else{        //here different from OJ solution
int res1 = helper(num,mid+1,end);
int res2 = helper(num,start,mid-1);
return Math.min(res1,res2);
}
}//end while
return Math.min(num[start],num[end]);
}
``````

}

The solution relimit the array size one element at a time, it sure will degenerate to N if encountering multiple duplicates array. But think of whenever encountering three equal numbers at three points(num[start]==num[mid]==num[end]), just split the array and run the binarysearch method respectively in lower and upper half, that would make the solution in time complexity of 2log(N), coz we are binary searching two halves, so still O(logN) in big o notation.

• I think it will degenerate to O(N) when the input is [1,1,1,1.....1,1].

T(N)=2*T(N/2)+O(1)