First Bad Version

---

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 have n versions [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 API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

---

Example 2:

Input: n = 1, bad = 1
Output: 1

---

Constraints:

• 1 <= bad <= n <= 2^31 - 1

---

Try this Problem on your own or check similar problems:

1. Guess Number Higher or Lower
2. Search Insert Position
3. Find First and Last Position of Element in Sorted Array

Solution:

Java

public int firstBadVersion(int n) {
    int start = 1, end = n;
    while(start < end){
        int mid = start + (end - start) / 2;
        if(isBadVersion(mid)){
            end = mid;
        }else{
            start = mid + 1;
        }
    }

    return start;
}

JavaScript

/**
 * 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) {
    let start = 1;
    let end = n;
    while (start < end) {
      let mid = Math.floor(start + (end - start) / 2);
      if (isBadVersion(mid)) {
        end = mid;
      } else {
        start = mid + 1;
      }
    }
    return start;
  };
};

Python

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        start = 1
        end = n
        while start < end:
            mid = start + (end - start) // 2
            if isBadVersion(mid):
                end = mid
            else:
                start = mid + 1
        return start

C++

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int start = 1;
        int end = n;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (isBadVersion(mid)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(logn)
• Space Complexity: O(1)

---

Explanation:

We perform binary search using the isBadVersion and range 1..n, if we find a mid which has a bad version we don't exclude it with end - 1 since it could be our solution. But if the mid is not bad we can be sure that none of the previous versions were bad either, so we can skip that half of the range start = mid + 1. At the end of loop start and end will point to our solution (first bad version). Since it's a binary search we have logarithmic time complexity O(logn). To learn more about binary search and why we set int mid = start + (end - start) / 2; you can check Binary Search.