> For the complete documentation index, see [llms.txt](https://yyloumike.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yyloumike.gitbook.io/leetcode/binary-search/0278.-first-bad-version.md).

# 0278. First Bad Version

Easy  |  Binary Search  |  24 ms (94.52%),  14.2 MB (73.95%)

{% tabs %}
{% tab title=" ❓ Problem Statement " %}

> Source: [LeetCode - First Bad Version](https://leetcode.com/problems/first-bad-version/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0278-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 returns whether `version` is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* `1 <= bad <= n <= 2^31 - 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.

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

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
**Binary Search** Problem\
Sorted array to find a **minimum number that is the first bad version.**
{% endhint %}

#### **Boundary / Search Space**

> Left (Minimum) = 1 (first version)\
> Right (Maximum) = n **(last element could be the answer)**

#### **Condition**

> While Loop = Left < Right\
> Return = isBadVersion(mid) == True

#### **Return Value**

> Left (as index)
> {% endtab %}
> {% endtabs %}

{% tabs %}
{% tab title=" 🤖 Python3" %}

```python
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        # (base case)
        if n == 1: return 1
        if n == 2: return 1 if isBadVersion(1) else 2
        
        # ==================================================
        #  Binary Search                                   =
        # ==================================================
        # time  : O(log(n))
        # space : O(1)

        l, r = 1, n
        while l < r:
            mid = (l + r) // 2
            
            if isBadVersion(mid): r = mid
            else: l = mid + 1
                
        return l
```

{% endtab %}

{% tab title=" 🤖 Java" %}

```java
/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    /**
     * @time  : O(log(n))
     * @space : O(1)
     */
    
    public int firstBadVersion(int n) {
        /* base case */
        if (n == 1) return 1;
        
        int l = 1, r = n;
        while(l < r) {
            int mid = l + (r - l) / 2;
            
            if(isBadVersion(mid)) r = mid;
            else l = mid + 1;
        }
        
        return l;
    }
}
```

{% endtab %}
{% endtabs %}