Coding Challenge Practice - Question 84

Say you have multiple versions of a program, write a program that will find and return the first bad revision given an isBad(version) function.

The boilerplate code:

function firstBadVersion(isBad) {
    // firstBadVersion receives a check function isBad
  // and should return a closure which accepts a version number(integer)
  return (version) => {
    // write your code to return the first bad version
    // if none found, return -1
  }
}

Create a search range. Start from version 1 to version.

let left = 1;
let right = version;

If there's no bad version, return -1

let result = -1;

Check the middle version. If it is bad, save it and check the left for an earlier bad version.

 while(left <= right) {
      const mid = Math.floor((left + right) / 2)

      if(isBad(mid)) {
        result = mid;
        right = mid - 1;
      }

If the middle version is not bad, the first bad version is to the right because all versions after the first bad version are bad, but not before.

else {
  left = mid + 1;
}

If a bad version was found, return the smallest one.

return result;

The final code

function firstBadVersion(isBad) {
  return (version) => {
    let left = 1;
    let right = version;
    let result = -1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);

      if (isBad(mid)) {
        // mid is bad, save it and search left side
        result = mid;
        right = mid - 1;
      } else {
        // mid is good, search right side
        left = mid + 1;
      }
    }

    return result;
  };
}

That's all folks!