First Bad Version

Problem

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.

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version.

Analysis

We should use binary search to get a logarithmatic time.

One important thing to keep in mind is that (left + right)/2 can actually cause overflow! Interesting discussion of that in the solution as follows:

If you are setting mid=left+right2mid = \frac{left + right}{2}mid=2left+right​, you have to be very careful. Unless you are using a language that does not overflow such as Python, left+rightleft + rightleft+right could overflow. One way to fix this is to use left+right−left2left + \frac{right - left}{2}left+2right−left​ instead.

If you fall into this subtle overflow bug, you are not alone. Even Jon Bentley’s own implementation of binary search had this overflow bug and remained undetected for over twenty years.

Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while (left < right) {
            int mid = left + (right - left)/2;
            if (isBadVersion(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

We should compare left <= right since otherwise we will end up missing one.

Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (isBadVersion(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};