O(logn) Java Accept Solution Binary Search


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

  • 0
    R
    This post is deleted!

  • 0
    K

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


  • 0
    S

    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.


  • 0
    S

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


  • 0
    S

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

  • 0
    J

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


  • 0
    Z

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


  • 0
    S

    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


  • 0
    H
    This post is deleted!

  • 2
    H

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

  • 0
    W

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


  • 0
    H

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


Log in to reply
 

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