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


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


  • 0
    Z

    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)


  • 0
    X

    The complexity of your answer is still O(N).


Log in to reply
 

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