# O(logn) Java Accept Solution Binary Search

• ``````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/2-1] > 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.length-num.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/2-1] > num[num.length-1]){
return findMin(second);
}else if(num[num.length/2-1] < num[num.length-1]){
return findMin(first);
}else{
if(num[num.length/2] < num[num.length-1]){
return findMin(second);
}else if(num[0] < num[num.length/2-1]){
return findMin(first);
}else{
return findMin(second);
}
}

}
}``````

• This post is deleted!

• when you assign the values of first[ ] and second[ ],the time complexity is beyond O(logn),namely,O(n).

• 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.

• You're right. Should send the entire array with begin and end index instead of new array. I'll repost it.

• 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.length-1);
}

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[middle-1] > num[middle] && num[middle] < num[middle+1]){return num[middle];}
if(num[middle-1] > num[end]){
return findMin(num,middle,end);
}else if(num[middle-1] < num[end]){
return findMin(num,begin,middle-1);
}else{
if(num[middle] < num[end]){
return findMin(num,middle,end);
}else if(num[begin] < num[middle-1]){
return findMin(num,begin,middle-1);
}else{
return findMin(num,middle,end);
}
}

}
}``````

• how about the case "444,404,4,444,444", you can just pass the case like "444,444,4,404,444"

• 444,404,4,444,444 is not a valid input. check the problem.

• 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

• This post is deleted!

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

• I don't think your algorithm is Log(n)
In worst case, deleting duplicate elements costs O(N).

• I agree. I was referring the average time complexity. For this problem, worst case should be O(n).

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