Question 3 - First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you havenversions[1, 2, ..., n]and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an APIbool isBadVersion(version)which will return whetherversionis bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Solution

/**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        var start = 1;
        var end = n;
        var mid = parseInt(n/2);

        while(start < end){
            if(!isBadVersion(mid)){
                start = mid + 1;
            }else{
                end = mid
            }
            mid = parseInt((start + end) / 2);
        }
        return start;
    };
};

Discussion

This question was a bit of a challenge because I'd never seen a question on leetcode defined like this. I didn't understand where to place my code, however after a bit of research I figured it out. Now the important bit in this question is that we should minimize the number of calls to the API. Of course I totally ignored this and wrote a for loop decreasing from n to 1. If I encountered a bad version, I returned that number.

I basically did a linear search and returned the first bad version I found. A more efficient search algorithm is the binary search algorithm. If you're unfamiliar with this algorithm, then take some time to read through the article at that link. You should be fully equipped to understand the answer after reading.

After implementation of this binary search algorithm, my solution was accepted.

var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        var start = 1;
        var end = n;
        var mid = parseInt(n/2);


    };
};

We start at 1 and end at n (n is the current version number). We also define the middle number as the integer value of n divided by 2. Integer values are always whole numbers so we have no decimal points.

var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        var start = 1;
        var end = n;
        var mid = parseInt(n/2);

        while(start < end){
            if(!isBadVersion(mid)){
                start = mid + 1;
            }else{
                end = mid
            }
            mid = parseInt((start + end) / 2);
        }
        return start;
    };
};

We then start our while loop to continue searching until the value of start is less than the value of end. We check if the mid value is a bad version and if not, we change the value of start to mid + 1. If mid is a bad version then we set the end value to be mid.

After our while loop is done, we return the value of start (which is the result of our search).