Java binary search with recursive implement


  • 5
    S

    /* The isBadVersion API is defined in the parent class VersionControl.
    boolean isBadVersion(int version); */

    public class Solution extends VersionControl {

    public int firstBadVersion(int n) {
        
        if(n==0) {
            return 0;
        }
    
       return helper(n,1,n);
    }
    
    
    public int helper(int n, int start, int end) {
        
        if(start>=end) {
            return start;
        }
        int middle = start+(end-start)/2;
        
        if(isBadVersion(middle)) {
            return helper(n,start,middle);
        } else {
            return helper(n,middle+1,end);
            
        }
    }
    

    }


  • 0
    W

    Hi, it seems n is of no use in your function helper
    BTW: thanks a lot, I have alomost same answer, however I didn't deal with (b-a)/2 + a, for stackoverflow, you helped me figure it out.


  • 0
    W

    Do you know the difference between (b-a)/2 + a and (b+a)/2 ? Why this will cause stackoverflow?


  • 0
    K
    This post is deleted!

  • 0
    G
    This post is deleted!

Log in to reply
 

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