# LeetCode 278: First Bad Version

## Problem Restatement

We have versions numbered from `1` to `n`.

At some version, the product becomes bad. Because each version is built from the previous one, every version after the first bad version is also bad.

So the versions look like this:

```python
good, good, good, bad, bad, bad
```

We are given an API:

```python
isBadVersion(version)
```

It returns `True` if the version is bad and `False` if the version is good.

We need to find the first bad version while making as few API calls as possible. The source constraint is `1 <= bad <= n <= 2^31 - 1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n`, the latest version number |
| API | `isBadVersion(version)` |
| Output | The first bad version |
| Versions | Numbered from `1` to `n` |

Function shape:

```python
# The isBadVersion API is already defined.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        ...
```

## Examples

For:

```python
n = 5
bad = 4
```

The API behaves like this:

```python
isBadVersion(1) == False
isBadVersion(2) == False
isBadVersion(3) == False
isBadVersion(4) == True
isBadVersion(5) == True
```

The first bad version is:

```python
4
```

For:

```python
n = 1
bad = 1
```

There is only one version, and it is bad.

So the answer is:

```python
1
```

## First Thought: Linear Scan

The most direct solution checks versions from left to right.

```python
for version in range(1, n + 1):
    if isBadVersion(version):
        return version
```

This works because the first time we see a bad version, that version must be the answer.

Code:

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

## Problem With Linear Scan

The linear scan may call the API `n` times.

Since `n` can be as large as `2^31 - 1`, a linear scan can be too slow.

We need to use the sorted structure of the answers.

The versions form a monotonic boolean sequence:

```python
False, False, False, True, True, True
```

We need the first `True`.

That is a binary search problem.

## Key Insight

If we check a middle version `mid`, there are two cases.

If:

```python
isBadVersion(mid) == True
```

then `mid` is bad. The first bad version may be `mid`, or it may be earlier. So we keep the left half, including `mid`.

If:

```python
isBadVersion(mid) == False
```

then `mid` is good. The first bad version must be after `mid`. So we discard `mid` and everything before it.

This lets us remove about half of the remaining versions on every API call.

## Algorithm

Use binary search over the version range `[1, n]`.

Initialize:

```python
left = 1
right = n
```

While `left < right`:

1. Compute the middle version.
2. If `mid` is bad, move `right` to `mid`.
3. If `mid` is good, move `left` to `mid + 1`.

When the loop ends, `left == right`.

That position is the first bad version.

## Correctness

At all times, the first bad version is inside the current range `[left, right]`.

At the start, the range is `[1, n]`, so it contains the first bad version.

On each step, we inspect `mid`.

If `mid` is bad, every version after `mid` can be ignored because `mid` itself is already bad. The first bad version must be either `mid` or some earlier version. So setting `right = mid` keeps the answer inside the range.

If `mid` is good, then `mid` and every version before it cannot be the first bad version. So setting `left = mid + 1` keeps the answer inside the range.

Each step preserves the invariant that the answer is inside `[left, right]`.

The loop stops when `left == right`. Since the range contains the answer and has only one version left, that version must be the first bad version.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log n)` | Each API call removes about half the search range |
| Space | `O(1)` | Only two pointers are stored |

## Implementation

```python
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left = 1
        right = n

        while left < right:
            mid = left + (right - left) // 2

            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1

        return left
```

## Code Explanation

We search inside the inclusive range:

```python
left = 1
right = n
```

The loop continues while more than one possible answer remains:

```python
while left < right:
```

We compute the middle this way:

```python
mid = left + (right - left) // 2
```

In Python, `(left + right) // 2` is safe too. The longer form is common because in languages with fixed-size integers, it avoids overflow.

If `mid` is bad:

```python
if isBadVersion(mid):
    right = mid
```

we keep `mid`, because `mid` may be the first bad version.

If `mid` is good:

```python
else:
    left = mid + 1
```

we discard `mid`, because the answer must be later.

Finally:

```python
return left
```

At this point, `left` and `right` are equal, and they point to the first bad version.

## Testing

LeetCode provides the `isBadVersion` API. For local testing, we can simulate it with a closure.

```python
def make_solution(first_bad):
    def isBadVersion(version: int) -> bool:
        return version >= first_bad

    class Solution:
        def firstBadVersion(self, n: int) -> int:
            left = 1
            right = n

            while left < right:
                mid = left + (right - left) // 2

                if isBadVersion(mid):
                    right = mid
                else:
                    left = mid + 1

            return left

    return Solution()

def test_first_bad_version():
    assert make_solution(4).firstBadVersion(5) == 4
    assert make_solution(1).firstBadVersion(1) == 1
    assert make_solution(1).firstBadVersion(10) == 1
    assert make_solution(10).firstBadVersion(10) == 10
    assert make_solution(7).firstBadVersion(20) == 7

    print("all tests passed")

test_first_bad_version()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 5, bad = 4` | Standard example |
| `n = 1, bad = 1` | Smallest valid input |
| `bad = 1` | First version is already bad |
| `bad = n` | Only the last version is bad |
| Middle bad version | Normal binary search behavior |