First Bad Version

Question (LC.278)

Given the last version number, find the first corrupted version.

Example

I: [T,T,T,F,F,F,F,F], 8
O: 4

What if there are no bad versions? Return 0

Brute Force

Linear scan all the versions and find the first one

public class Solution extends VersionControl {
    public int firstBadVersion(int lastVersion) {
        int v;
        for (v = 1; v <= lastVersion; v++) {
            if (isBadVersion(v)) {1
                return v;
            }
        }
        return 0;
    }
}

Time limit exceeded with input size

2126753390 versions
1702766719 is the first bad version.

Binary Search

Since the search space well-ordered, we can decompose it with an O(1) check.

public int firstBadVersion(int lastVersion) {
    int start = 1, end = lastVersion, mid;
    while (start + 1 < end) {
        mid = start + (end - start) / 2;
        if (isBadVersion(mid)) { // false go left
            end = mid;
        } else { // true go right
            start = mid;
        }
    }
    // stop when two pointers are adjacent to each other
    if (isBadVersion(start)) {
        return start;
    } else if (isBadVersion(end)) {
        return end;
    } else {
        return 0; // no bad versions
    }
}