L74 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 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.

2分地找...

public int firstBadVersion(int n) {
    if (n < 1) {
        return -1;
    }

    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;
    } else {
        return end;
    }
}