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 bad commit

def firstBadVersion(self, n: int) -> int:
    for i in range(1, n+1):
        if isBadVersion(i):
            return i

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
    }
}

def firstBadVersion(self, n: int) -> int:
    
    # while loop is the base case 
    
    start = 1
    end = n 
    
    while (end - start + 1 > 2):
        middle = (start + end) // 2 
        
        if isBadVersion(middle):
            end = middle 
        else:
            start = middle + 1 
    
    if isBadVersion(start):
        return start
    elif isBadVersion(end):
        return end
    else:
        return -1 

Divide and Conquer

This is more like just dividing.

How to select middle index

If we use this simple formula $\frac{s + e}{2}$ , then left section should be $[s, m]$and right section should be $(m, e]$for even distribution in these 2 cases. We can get smart to exclude the middle element if it is not the target but that is a minor optimization.

Recursion solution is easier to understand and write. But I suspect the performance is worse (at least for space efficiency).

The two pointer solution above is harder to write but is a little more performant.

Recursive solution	Two pointer solution
Runtime: 32 ms Memory Usage: 14.4 MB	Runtime: 32 ms Memory Usage: 14.2 MB

Turns out the performance difference is minimal. I don't think a $\log{n}$algorithm can cause stack overflow.

class Solution:
    
    # isBadVersion(version: int) -> bool 

    
    def firstBadVersion(self, n: int) -> int:

        if n < 1:
            return -1 
        
        return self.searchHelper(1, n)
        
    def searchHelper(self, start: int, end: int) -> int:
        
        length = end - start + 1 
        
        # base case 
        if length <= 2:
            if isBadVersion(start):
                return start
            elif isBadVersion(end):
                return end
            else:
                return -1 
        
        # divide 
        
        middle = (start + end) // 2 
        
        if isBadVersion(middle):
            return self.searchHelper(start, middle)
        else:
            return self.searchHelper(middle+1, end)

Note: / does true division. // does floor division.