## Problem

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

## Solution

Simple binary search

### Recursive

```
class Solution : VersionControl {
func firstBadVersion(_ n: Int) -> Int {
return findBadVersion(1, n)
}
func findBadVersion(_ left: Int, _ right: Int) -> Int {
let middle = left + (right - left) / 2
if (left >= right) {
return left
}
if isBadVersion(middle) {
return findBadVersion(left, middle)
}else{
return findBadVersion(middle+1, right)
}
}
}
```

### Iterative

```
class Solution : VersionControl {
func firstBadVersion(_ n: Int) -> Int {
var left = 1, right = n
while left < right {
let middle = left + (right - left) / 2
if isBadVersion(middle) {
right = middle
}else {
left = middle + 1
}
}
return left
}
}
```