first-bad-version

First Bad Version – LeetCode 278

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.

Answer

Original

Code

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
 
class Solution {
public:
    /**
     * @param n: An integers.
     * @return: An integer which is the first bad version.
     */
    int findFirstBadVersion(int n) {
        if (n < 1) {
            return -1;
        }

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

思路

使用二分查找寻找第一个坏的版本，时间复杂度$O(log{n})$，空间复杂度$O(1)$。

Better

思路

还没看到更好的思路。