LeetCode - FirstBadVersion  

by ne on 2022-02-16 under Algo/DS/Problems tagged with leetcode

Hi,
The problem description is in the comments above the solution below.

The problem belongs to LeetCode, you can try out it yourself on their platform.


/**
 * 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.
 */
public class FirstBadVersion {
    // this method is provided by leetcode , adding dummy logic here.
    static boolean isBadVersion(int m) {
        return false;
    }

    public int firstBadVersion(int n) {
        int b = 1;
        int e = n;
        while (b < e) {
            int m = b + (e - b) / 2;
            if (isBadVersion(m)) {
                e = m;
            } else {
                b = m + 1;
            }
        }
        return b;
    }
}