Hà Phan（河）

## Problem

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

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