# First Bad Version

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

Since we need to check *current index and its immediate right (or left) neighbor, so intuition is to consider using Template #2, or Template #3. But actually using Template #1 also works, the low is the index we need.*

**How to prove / check if the result would be right as first bad version?**

> A helpful tip to quickly prove the correctness of your binary search algorithm during an interview. We just need to test an input of **size 2**. Check if it reduces the search space to a single element (which must be the answer) for both of the scenarios above. If not, your algorithm will never terminate.

**Initialization:**

> In our case, we indicate leftleft and rightright as the boundary of our search space (both inclusive). This is why we initialize left = 1 and right = n.

Example

```
F T
```

## Solution

Using Binary Search Template #1

```java
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int lo = 1;
        int hi = n;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (isBadVersion(mid)) {
                hi = mid - 1;
            }
            else {
                lo = mid + 1;
            }
        }

        return lo;
    }
}
```

Using Binary Search Template #2

```java
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;
        } else {
            left = mid + 1;
        }
    }
    return left;
}
```

Using Binary Search Template #3

```java
/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        // left + 1 == right or left + 1 > right
        if (isBadVersion(left) ) {
            return left;
        } else if (isBadVersion(right)) {
            return right;
        }
        return -1;
    }
}
```