# 278. First Bad Version

# 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 returns whether `version`

is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

**Example 1:**

**Input:** n = 5, bad = 4 **Output:** 4 **Explanation:**call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true Then 4 is the first bad version.

**Example 2:**

**Input:** n = 1, bad = 1 **Output:** 1

**Constraints:**

`1 <= bad <= n <= 2`

^{31}- 1

# Solution

There's some cool things about this problem. For instance, you may notice that:

` mid = (start+end)) / 2;`

causes overflows if you use this. That's because when start + end are around `INT_MAX`

it will cause an overflow since you can't add 2 `INT_MAX`

s together.

Instead, use this method:

` mid = start+(end-start)/2;`

```
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):
class Solution(object):
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
# this is a binary search, we need 2 pointers for this.
left, right = 0, n - 1
while left <= right:
mid = left + (right - left) / 2
if isBadVersion(mid) == False:
left = mid + 1
else:
right = mid - 1
return left
```

I suggest this article for studying binary search: