> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/divide_and_conquer/binary_search/first-bad-version.md).

# First Bad Version

## Question ([LC.278](https://leetcode.com/problems/first-bad-version/))

> 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 

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

```java
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.

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

```python

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&#x20;

This is more like just dividing.&#x20;

![How to select middle index](/files/-MP1JgfWjIVKUD5tbOSC)

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.&#x20;

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

The two pointer solution above is harder to write but is a little more performant.&#x20;

| Recursive solution                                | Two pointer solution                              |
| ------------------------------------------------- | ------------------------------------------------- |
| <p>Runtime: 32 ms</p><p>Memory Usage: 14.4 MB</p> | <p>Runtime: 32 ms</p><p>Memory Usage: 14.2 MB</p> |

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

```python
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.&#x20;