> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/278-first-bad-version.md).

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

**Credits:**\
Special thanks to[@jianchao.li.fighter](https://leetcode.com/discuss/user/jianchao.li.fighter)for adding this problem and creating all test cases.

**The Idea:** Binary search until we are able to converge into the region that separates the last good version to the first bad version.

```
[1 1 1 1 1 1 1 1 1 1 0 0 0 0 0]
                   ^
```

**Complexity:** O(logn) time and O(1) space through iterative binary search

```python
# 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
        """
        left, right = 1, n
        while left < right:
            mid = int(left + ((right - left) >> 1))
            if not isBadVersion(mid):  # search right
                left = mid + 1
            else:                      # search left
                right = mid - 1

        if isBadVersion(left):
            return left
        else:
            return left + 1
```