Why am I getting a stack overflow?


  • 0
    J

    I've been working on first bad version for a while, and I can't figure out what I'm doing wrong. I keep getting "Runtime Error Message: Line 22: java.lang.StackOverflowError" when I try to recursively call searchBad(). Can anyone shine some light on this?

    public class Solution extends VersionControl {
    
    public int firstBadVersion(int n) {
        return searchBad(n, 1);
    }
    
    private int searchBad(int hi, int lo){
        if(isBadVersion(lo)){
                return lo;
        }
        int mid = hi/2 + lo/2;
        if(isBadVersion(mid)){
            if(isFirstBad(mid))
                return mid;
            else
                return searchBad(mid, lo);
        }
        else{
            return searchBad(hi, mid);
        }
    }
    
    private Boolean isFirstBad(int n){
        if(n > 2){
            if(isBadVersion(n-1))
                return false;
            else
                return true;
        }
        else
            return true;
        }
    }

  • 0
    T

    in the case which mid = lo and lo is not bad, you are continuously calling searchBad(hi,lo). I don't want to give too many details; you are better off finding a solution on your own. Best of luck!


Log in to reply
 

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