HàPhan 河

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

Then 4 is the first bad version.
``````

## Solution

Simple binary search

### Recursive

``````class Solution : VersionControl {
func firstBadVersion(_ n: Int) -> Int {
}

func findBadVersion(_ left: Int, _ right: Int) -> Int {
let middle = left + (right - left) / 2
if (left >= right) {
return left
}
}else{
}
}
}
``````

### Iterative

``````class Solution : VersionControl {
func firstBadVersion(_ n: Int) -> Int {

var left = 1, right = n

while left < right {
let middle = left + (right - left) / 2