FirstBadVersion [source code]

public class FirstBadVersion {
static
/******************************************************************************/
/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int lo = 1, hi = n;
        if (!isBadVersion(hi)) return n + 1;
        if (isBadVersion(lo)) return 0;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isBadVersion(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return hi;
    }
}
/******************************************************************************/
static class VersionControl {
    boolean isBadVersion (int version) {
        return false;
    }
}

    public static void main(String[] args) {
        FirstBadVersion.Solution tester = new FirstBadVersion.Solution();
    }
}

注意给的这个API里面的这个version是0-based(也就是index)还是1-based(也就是value);

这个题目其实想到Binary Search并不难, 关键是这个问题怎么把Binary Search适应到这个问题上;

Binary Search无论最后是hit还是miss, 核心判断其实都在最后一个长度为2的iteration. 在大逻辑有把握的情况下, 最后的分析就针对这一个iteration就行了; 注意在考虑这个iteration的时候, invariant是: lo一定是bad, hi一定是good;

脑子里visual的时候可以用白和黑来代表好坏;

通过分析最后一个iteration, 可以发现这题这个循环的header不能取等号, 不然就是死循环; 包括这一题左移的时候, hi = mid而不是mid - 1, 这个是因为mid仍然有可能是我们想要的答案(the first bad);

这样的精致分析之后, 直接AC. 经过了这个题目应该说之后对于Binary Search的理解就加强很多了; 最后的速度是20ms (14%), 倒是不怎么理想; 不过好像大部分代码其实都差不多. 题目也比较老了, 速度就不纠结了;

editorial解跟我的代码几乎一模一样, 不过他们没有进行两个base case的判断;

想想确实是不必要的;

discussion好像也没有什么特别新奇的解法;

Problem Description

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 will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Difficulty:Easy
Total Accepted:102.6K
Total Submissions:408.7K
Contributor: LeetCode
Companies
facebook
Related Topics
binary search
Similar Questions
Search for a Range Search Insert Position Guess Number Higher or Lower