public class Solution {
public int findMin(int[] num) {
// base case
if(num.length == 1){return num[0];}
if(num.length == 2){return num[0] >num[1]? num[1]:num[0];}
// recursive call
if(num[num.length/21] > num[num.length/2] && num[num.length/2] < num[num.length/2+1]){return num[num.length/2];}
int first[] = new int[num.length/2];
int second[] = new int[num.lengthnum.length/2];
for(int i = 0;i < first.length;i++){first[i] = num[i];}
for(int i = 0;i < second.length;i++){second[i] = num[i+num.length/2];}
//return num[0] < num[num.length/2]? findMin(second):findMin(first); // it's the previous one
if(num[num.length/21] > num[num.length1]){
return findMin(second);
}else if(num[num.length/21] < num[num.length1]){
return findMin(first);
}else{
if(num[num.length/2] < num[num.length1]){
return findMin(second);
}else if(num[0] < num[num.length/21]){
return findMin(first);
}else{
return findMin(second);
}
}
}
}
O(logn) Java Accept Solution Binary Search


Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example
Pay attention to "Writing code? Select all code then click on the {} button to preserve code formatting.” above text editor.

To make it O(logN), I pass the entire array with begin and end index specified instead of new sub array. This should make sense.
public class Solution { public int findMin(int[] num) { return findMin(num,0,num.length1); } private int findMin(int num[],int begin,int end){ if(end == begin){return num[begin];} if(end  begin == 1){return num[begin] >num[end]? num[end]:num[begin];} int middle = (begin+end+1)/2; if(num[middle1] > num[middle] && num[middle] < num[middle+1]){return num[middle];} if(num[middle1] > num[end]){ return findMin(num,middle,end); }else if(num[middle1] < num[end]){ return findMin(num,begin,middle1); }else{ if(num[middle] < num[end]){ return findMin(num,middle,end); }else if(num[begin] < num[middle1]){ return findMin(num,begin,middle1); }else{ return findMin(num,middle,end); } } } }

I think jasonwbw's talking about cases like "4,0,4,4,4" and "4,4,4,0,4". Yeah. I should not have passed cases like that. My algorithm is incorrect. So you hold that there is no binary search when duplicate exists. I think it is really true that you cannot decide which half to do the recursion call in that case. So, the problem could be O(n) in run time. I just thought it is weird because you can get the minimum of any array in O(n). Please let me know if you find

To make it Log(n). The more simply idea is to cut off all the duplicate element in the font.
Then do the normal binary search. Hope this helps.public int findMin(int[] num) { return binarysearch(num, 0, num.length  1); } public int binarysearch(int[] num, int i, int j) { int k = i; // move cursor to the first element that is not the same with the last one while (k<=j && num[k] == num[j]) k++; if (k > j) { return num[i]; } i = k; //The same binarysearch as the last problem. if (num[i] < num[j]) return num[i]; k = (i+j)/2; if(num[k]>=num[i]) { return binarysearch(num, k+1, j); } else { return binarysearch(num, i, k); } }