# First Bad Version
**Difficulty:** EASY
[External](https://leetcode.com/problems/first-bad-version)
Canonical: https://scaleengineer.com/dsa/problems/first-bad-version
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
---
## 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 <= 231 - 1`

# Approaches
## Linear Search
Iterate through each version from 1 to n and check if it's a bad version using the isBadVersion API. Return the first bad version found.
**Time:** O(n) - where n is the number of versions, as we might need to check all versions in the worst case · **Space:** O(1) - only using a constant amount of extra space
**Pros:** Simple and easy to understand; Works for small inputs; Minimal space requirement
**Cons:** Inefficient for large inputs; Makes too many API calls; Does not minimize the number of calls to the API as required
### Explanation
The linear search approach is the most straightforward solution. We start checking each version from 1 up to n using the isBadVersion API. As soon as we find a bad version, we return it since it will be the first bad version (as all versions after a bad version are also bad).

```java
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        for (int version = 1; version <= n; version++) {
            if (isBadVersion(version)) {
                return version;
            }
        }
        return n;
    }
}
```

In this approach, we simply use a for loop to check each version. When we find the first bad version, we return it immediately.
### Algorithm
1. Start iterating from version 1 to n
2. For each version, call isBadVersion(version)
3. If isBadVersion returns true, return the current version
4. If no bad version is found, return n

## Binary Search
Use binary search to efficiently find the first bad version by eliminating half of the search space in each step.
**Time:** O(log n) - where n is the number of versions, as we divide the search space in half in each iteration · **Space:** O(1) - only using a constant amount of extra space
**Pros:** Efficient logarithmic time complexity; Minimizes the number of API calls; Works well for large inputs; Handles integer overflow properly
**Cons:** Slightly more complex implementation than linear search; Requires understanding of binary search concept
### Explanation
The binary search approach is optimal for this problem as it minimizes the number of API calls. Since all versions after a bad version are also bad, we can use binary search to find the transition point from good to bad versions.

```java
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}
```

In this approach:
1. We maintain two pointers, left and right, initially pointing to 1 and n respectively
2. We calculate the middle point using mid = left + (right - left) / 2 to avoid integer overflow
3. If the middle version is bad, we know the first bad version is either this one or earlier
4. If the middle version is good, we know the first bad version must be after this one
5. We continue this process until left and right converge to the first bad version
### Algorithm
1. Initialize left = 1 and right = n
2. While left < right:
   - Calculate mid = left + (right - left) / 2
   - If isBadVersion(mid) is true, set right = mid
   - If isBadVersion(mid) is false, set left = mid + 1
3. Return left

# Solutions
### Java

```java
/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */ public class Solution extends VersionControl { public int firstBadVersion ( int n ) { int left = 1 , right = n ; while ( left < right ) { int mid = ( left + right ) >>> 1 ; if ( isBadVersion ( mid )) { right = mid ; } else { left = mid + 1 ; } } return left ; } }
```

### JavaScript

```javascript
/** * Definition for isBadVersion() * * @param {integer} version number * @return {boolean} whether the version is bad * isBadVersion = function(version) { * ... * }; */ /** * @param {function} isBadVersion() * @return {function} */ var solution = function ( isBadVersion ) { /** * @param {integer} n Total versions * @return {integer} The first bad version */ return function ( n ) { let left = 1 ; let right = n ; while ( left < right ) { const mid = ( left + right ) >>> 1 ; if ( isBadVersion ( mid )) { right = mid ; } else { left = mid + 1 ; } } return left ; }; };
```

### CPP

```cpp
// The API isBadVersion is defined for you. // bool isBadVersion(int version); class Solution { public: int firstBadVersion ( int n ) { int left = 1 , right = n ; while ( left < right ) { int mid = left + (( right - left ) >> 1 ); if ( isBadVersion ( mid )) { right = mid ; } else { left = mid + 1 ; } } return left ; } };
```

### Python

```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 ): """ :type n: int :rtype: int """ left , right = 1 , n while left < right : mid = ( left + right ) >> 1 if isBadVersion ( mid ): right = mid else : left = mid + 1 return left
```