278. First Bad Version (Easy)

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 1: Binary Search O(log n); O(1)

这种写法API调用最少，但是要问：Can I assume that there must exist a bad version so that I don't need to handle the case that all versions are good?

    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; //mid can be the first bad version
            } else {
                start = mid + 1; //mid version is good so we can exclude it.
            }
        }
        return start;
    }

Solution 2: Binary Search O(log n); O(1)

如果有全是good version的case，必须这么写了。

    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;
            }
        }
        if (isBadVersion(start)) {
            return start;
        }
        return -1;
    }

Solution 3: Binary Search O(log n); O(1) 九章二分模板，这题不推荐用

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

Follow Up:

1.多加了一个 转化时间到产品代号的api, 具体我也说不清楚，反正核心算法就是binary search

bad version 那道题他变种的面目全非了，直接导致我做这道题用了20分钟。。。。

2.如果有k台机器，如何parallel （博士的面经）
这个题没让写代码，就说了一下思路，我回答的大概就是把区间分成k+1份，然后这样就要K个分割点让K台机器并行的调用isBad()函数，然后遍历得到的结果，会有一个点i和其相邻点(i+1)的结果不一样，这样就把区间范围缩小到(i, i+1)，重复之前的过程知道找到为止。小哥说ok也没再继续问