First Bad Version using recursion debugging


  • 0
    C
    // Forward declaration of isBadVersion API.
        bool isBadVersion(int version);
    //int helperFirstBadVersion(int n, int left, int right);
        class Solution {
    public:
        int firstBadVersion(int n) {
            if (n <=1) {
                return n;
            }
            return helperFirstBadVersion(1, n);
        }
        
        int helperFirstBadVersion(int left, int right) {
        if (left >= right) {
            return left;
        }
        int mid = left + (right -left) / 2;
        if (isBadVersion(mid)) {
            return helperFirstBadVersion(left, mid);
        } else {
            return helperFirstBadVersion(mid, right);
        }
    }
    };
    

    This is my recursion version of first Bad Version problem. I ran it but got compiler error.Also I tried to put the helper function outside of the class definition but still got compiler error. I tried to figure out why but haven't understood why.


  • 0
    Q

    if (left >= right) {
    return left;
    }

    it's useless.I know you want to exchange the larger one as the second parameter of helperFirstBadVersion(),but it doesnot work like you want.


  • 1
    W

    It is not the right way to implement a binary search. Suppose left = 1, right = 2, then mid = 1 and it is not a bad version. The recursion will trap in left = 1, right = 2, mid = 1.

    return helperFirstBadVersion(mid, right);
    

    should be

    return helperFirstBadVersion(mid+1, right);

  • 0

    I tried it and didn't get a compiler error. Is your question tag correct and you tried to submit this as a C program? Then it does get a compiler error. Also, and most importantly and you should've told that right away: What compiler error did you get?


Log in to reply
 

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