Skip to main content

Binary Search

First Bad Version Solution in C++/Java/Python/JS

Problem Description:

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.
Illustration of the problem description

Examples:

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

Constraints:

  • 1 <= bad <= n <= 231 - 1

First Bad Version Problem

We are provided with a single integer n showing number of versions of a product. First few of them are good and then all others after these good ones are bad because a single bad version will lead to another bad version.
We need to find the first bad version out of all n versions using an API bool isBadVersion(version) which tells if a version is bad or not.
How would you approach this problem?...

Brute Force Approach

Intuition:

To build our First Bad Version Solution, the first thing we focus on is that out of all the versions from 0 to n there is some version i which is the first bad version and all the versions before it are good.

The search space is monotonic

One key observation that simplifies our approach is that the versions follow a monotonic pattern:

  • Before the first bad version (i): All versions are good.
  • Starting from the first bad version (i) onward: Every version is bad.

To determine i, we could take a brute-force approach where we check every version from 1 to n. We would call the function isBadVersion(version) for each version. The first time this function returns true, we know we have found the first bad version, and we simply return it.

💡
Try it yourself !

First Bad Version solution

For example, if we have n = 7 and the function isBadVersion(version) behaves as follows:

  • Version 1: Good
  • Version 2: Good
  • Version 3: Good
  • Version 4: Bad (First bad version)
  • Version 5: Bad
  • Version 6: Bad
  • Version 7: Bad

In this case, we would check versions 1, 2, and 3 before discovering that version 4 is bad, at which point we return 4 as the answer.

Illustration of Brute Force Approach

First Bad Version example

Input: n = 10 bad = 3 (bad value is not told to you)
Output: 3
Explanation: The first bad version of the 10 version is the 3rd version so we return 3.

Initialization

  1. The function firstBadVersion(n) is called with n = 10.
  2. A loop starts from i = 1 and runs until i <= n.
  3. The function isBadVersion(i) checks if the current version is bad.

Iterations

  • Iteration 1: i = 1
    • isBadVersion(1) is called → returns false
    • Since it's not bad, move to i = 2.
  • Iteration 2: i = 2
    • isBadVersion(2) is called → returns false
    • Since it's not bad, move to i = 3.
  • Iteration 3: i = 3
    • isBadVersion(3) is called → returns true
    • Since it's bad, the function returns 3 immediately.

Final Output

  • The first bad version found is 3, so the function returns 3.

Steps to write code

Step 1: Iterate Through Versions

  • Use a loop starting from i = 1 to n.

Step 2: Check for Bad Version

  • Call isBadVersion(i) to check if the current version is bad.

Step 3: Return the First Bad Version

  • If isBadVersion(i) returns true, return i immediately.

Step 4: Handle Edge Cases

  • If no bad version is found (though logically impossible in this problem), return -1.
Brute Force in All Languages
First Bad Version solution in C++ 
class Solution {
public:
    // Function to find the first bad version using brute force
    int firstBadVersion(int n) {
        // Iterate through all versions from 1 to n
        for (int i = 1; i <= n; ++i) {
            // Check if the current version is bad
            if (isBadVersion(i)) {
                // Return the first bad version found
                return i;
            }
        }
        // Return -1 if no bad version found
        return -1;
    }
};

First Bad Version solution in Java 
class Solution extends VersionControl {
    // Function to find the first bad version using brute force
    public int firstBadVersion(int n) {
        // Iterate through all versions from 1 to n
        for (int i = 1; i <= n; i++) {
            // Check if the current version is bad
            if (isBadVersion(i)) {
                // Return the first bad version found
                return i;
            }
        }
        // Return -1 if no bad version found
        return -1;
    }
}

First Bad Version solution in Python 
class Solution:
    # Function to find the first bad version using brute force
    def firstBadVersion(self, n: int) -> int:
        # Iterate through all versions from 1 to n
        for i in range(1, n + 1):
            # Check if the current version is bad
            if isBadVersion(i):
                # Return the first bad version found
                return i
        # Return -1 if no bad version found
        return -1

First Bad Version solution in Javascript 
/**
 * Simulates the API isBadVersion
 * @param {integer} version - Version number
 * @return {boolean} - Whether the version is bad
 */
function isBadVersion(version) {
    return version >= bad;
}

/**
 * @param {function} isBadVersion - API function
 * @return {function}
 */
var solution = function(isBadVersion) {
    return function(n) {
        // Iterate through all versions from 1 to n
        for (let i = 1; i <= n; i++) {
            if (isBadVersion(i)) {
                return i;
            }
        }
        return -1;
    };
};

First Bad Version Complexity Analysis

Time Complexity: O(n)

Step-by-Step Analysis

  1. The function iterates from i = 1 to n, checking each version one by one.
  2. Each call to isBadVersion(i) takes O(1) time.
  3. In the worst case, the bad version is at n, meaning the loop runs O(n) times.

Final Time Complexity: O(n) if (bad = n)

Space Complexity: O(1)

Auxiliary Space Complexity
Extra space used. Not the input space.

  • The function uses only a loop variable (i), which takes O(1) space.
  • No extra data structures (arrays, lists, or recursion stack) are used.
  • Therefore, the auxiliary space complexity is O(1).

Total Space Complexity
It consists is the overall space of the program

  • The function does not store any input explicitly.
  • It only reads n as an integer, which takes O(1) space.
  • Since no additional space is used apart from a few integer variables, the total space complexity is O(1).

Final Space Complexity

  • Auxiliary Space Complexity: O(1)
  • Total Space Complexity: O(1)

Is the brute force approach efficient?

Looking at the constraints we see n <= 231 -1. The complexity of our solution is O(n) in worst case. This corresponds approx 2147483647 operations at worst case. In one second leetcode and major competetive programming platforms allow at most 106 to 107 operations.

Here the value is beyond 109 so the solution won't get accepted. Hence we need to optimize our solution.

How would you optimize the First Bad Version Solution.

Optimal Approach

Intuition:

Now all we know is that we can't afford to iterate from version 1 to version n to check for the first bad version.

Let's choose some version between 1 and n, for example, the middle version (mid), and analyze whether we can strategically eliminate the part of the search space where we are certain that the first bad version cannot exist. This will help us focus on the part of the search space where we are most likely to find the answer.

💡
Try it yourself !

When we select the middle version (mid), we can call the API isBadVersion(mid) to check whether this version is bad or good. The API will return either:

  • true, indicating that mid is a bad version.
  • false, indicating that mid is a good version.

Based on this result, we can decide which half of the search space to continue looking into. Let’s break it down case by case.

Case 1: isBadVersion(mid) returns false

If isBadVersion(mid) returns false, that means mid is a good version. Since versions are monotonic (all versions before the first bad version are good), this also tells us that all versions from 1 to mid are also good. That means the first bad version cannot exist in this range, and we can completely ignore the left half of our search space. Instead, we need to continue searching towards the right of mid, as the first bad version must be somewhere after mid.

Example for Case 1:

Suppose n = 10 and the first bad version is 6. If we check mid = 5, and isBadVersion(5) returns false, we know:

Versions: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Result: G G G G G B B B B B (G = Good, B = Bad)

Since mid = 5 is good, the first bad version must be in [6, 7, 8, 9, 10], so we move our search to the right half.

Illustration of Case 1 of Optimal Approach

Case 2: isBadVersion(mid) returns true

If isBadVersion(mid) returns true, this means mid is a bad version. But we are not necessarily looking for just any bad version, we need to find the first bad version. This means that the bad version might be mid, or it could be somewhere earlier in the search space. Since we are unsure, we should eliminate the right half and continue searching in the left half to see if there is an even earlier bad version.

Example for Case 2:

Suppose n = 10 and the first bad version is 6. If we check mid = 5, and isBadVersion(5) returns true, we know:

Versions: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Result: G G G B B B B B B B (G = Good, B = Bad)

Since mid = 5 is bad, we now know that the first bad version must be in [1, 2, 3, 4, 5] So, we shift our search to the left half to find the first occurrence of a bad version.

Illustration of Case 2 of Optimal Approach

First Bad Version Algorithm

To efficiently find the first bad version LeetCode solution. We initialize two pointers, low = 1 and high = n. We repeatedly select the middle version (mid = (low + high) / 2) and check if it's bad using isBadVersion(mid).

  • If mid is bad, the first bad version could be at mid or earlier, so we set high = mid.
  • If mid is good, the first bad version must be after mid, so we set low = mid + 1.

We continue this process until low == high, where low points to the first bad version.

This process of narrowing down the search space until we find the answer is called binary search.

More about binary search here...

💡
Binary Search!
0:00
/1:10

Illustration of how Optimal Approach works.

First Bad Version example

Input: n = 10 bad = 3 (bad value is not told to you)
Output: 3
Explanation: The first bad version of the 10 version is the 3rd version so we return 3.

Initialization:

  • low = 1, high = 10

Iteration 1:

  • Compute mid: mid=low+(high−low)/2=1+(10−1)/2​=1+9/2​=1+4=5
  • isBadVersion(5) returns true, so update high = 5.

Iteration 2:

  • Compute mid: mid=low+(high-low)/2=1+(5−1)/2​=1+4/2​=1+2=3
  • isBadVersion(3) returns true, so update high = 3.

Iteration 3:

  • Compute mid: mid=low+(high-low)/2=1+(3−1)​/2=1+2/2​=1+1=2
  • isBadVersion(2) returns false, so update low = 3.

Exit Condition:

  • low = high = 3, the loop terminates.
  • Return 3 as the first bad version.

Steps to write code

Step 1: Initialization

  • Define the function firstBadVersion(int n).
  • Initialize two pointers:
    • low = 1 (starting version).
    • high = n (last version).

Step 2: Implement Binary Search

  • Use a while loop that runs while low < high.

3. Calculate the Middle Version

  • Compute mid using the formula: mid=low+(high−low)/2​
  • This avoids integer overflow compared to (low + high) / 2.

4. Check if mid is a Bad Version

  • Call isBadVersion(mid).
  • If mid is bad (true):
    • Set high = mid (search in the left half).
  • Else (false):
    • Set low = mid + 1 (search in the right half).

5. Return the First Bad Version

  • When low == high, exit the loop.
  • Return low as the first bad version.
Optimal Approach in All Languages
First Bad Version solution in C++ 
public:
    // Function to find the first bad version using brute force
    int firstBadVersion(int n) {
        // Initialize search range
        int low = 1, high = n;
        
        // Perform binary search
        while (low < high) {
            // Calculate mid-point to avoid overflow
            int mid = low + (high - low) / 2;
            
            // If mid is a bad version, search in the left half
            if (isBadVersion(mid)) {
                high = mid;
            }
            // Else search in the right half
            else {
                low = mid + 1;
            }
        }
        // The first bad version is found at 'low'
        return low;
    }
};

First Bad Version solution in Java 
class Solution extends VersionControl {
    // Function to find the first bad version using brute force
    public int firstBadVersion(int n) {
        // Initialize search range
        int low = 1, high = n;

        // Perform binary search
        while (low < high) {
            // Calculate mid-point to avoid overflow
            int mid = low + (high - low) / 2;

            // If mid is a bad version, search in the left half
            if (isBadVersion(mid)) {
                high = mid;
            }
            // Else search in the right half
            else {
                low = mid + 1;
            }
        }
        // The first bad version is found at 'low'
        return low;
    }
}

First Bad Version solution in Python 
class Solution:
    # Function to find the first bad version using brute force
    def firstBadVersion(self, n: int) -> int:
        # Initialize search range
        low, high = 1, n
        
        # Perform binary search
        while low < high:
            # Calculate mid-point to avoid overflow
            mid = low + (high - low) // 2
            
            # If mid is a bad version, search in the left half
            if isBadVersion(mid):
                high = mid
            # Else search in the right half
            else:
                low = mid + 1
        
        # The first bad version is found at 'low'
        return low

First Bad Version solution in Javascript 
/**
 * Simulates the API isBadVersion
 * @param {integer} version - Version number
 * @return {boolean} - Whether the version is bad
 */
function isBadVersion(version) {
    return version >= bad;
}

/**
 * @param {function} isBadVersion - API function
 * @return {function}
 */
var solution = function(isBadVersion) {
    return function(n) {
        // Initialize search range
        let low = 1, high = n;

        // Perform binary search
        while (low < high) {
            // Calculate mid-point to avoid overflow
            let mid = Math.floor(low + (high - low) / 2);

            // If mid is a bad version, search in the left half
            if (isBadVersion(mid)) {
                high = mid;
            }
            // Else search in the right half
            else {
                low = mid + 1;
            }
        }
        // The first bad version is found at 'low'
        return low;
    };
};

First Bad Version Complexity Analysis

Time Complexity: O(logn)

Step 1: Initialize Search Space:

  • We start with low = 1 and high = n.
  • The total number of elements to search is n.

Step 2: Binary Search Halving the Range:

  • Each iteration computes mid = low + (high - low) / 2.
  • If mid is a bad version, we move high = mid, else low = mid + 1.
  • This halves the search space in each step.

Step 3: Number of Iterations:

  • In the first iteration, the range is n.
  • In the second iteration, the range is n/2.
  • In the third iteration, the range is n/4.
  • This continues until the range reduces to 1.

Step 4: Solve for Iterations Needed:

  • We stop when the range becomes 1, i.e., when n/2k=1
  • Solving for k: n/2k=1 which reduces to k=log⁡(n)
  • This means the loop runs O(log n) times.

Space Complexity: O(1)

Auxiliary Space Complexity
The additional space used except input

  • The function only uses a few integer variables (low, high, mid).
  • No recursion or additional data structures (arrays, lists, etc.) are used.
  • Auxiliary space complexity: O(1) (constant space).

2. Total Space Complexity (Including Input Storage)

  • The input n is stored as an integer, which takes O(1) space.
  • No extra space is used apart from the function’s variables.
  • Total space complexity: O(1).

Final Space Complexity: O(1)

Similar Problems

Now we have successfully tackled this problem, let's try these similar problems:-

1. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

2. Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

3. Guess Number Higher or Lower

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API int guess(int num), which returns three possible results:

  • -1: Your guess is higher than the number I picked (i.e. num > pick).
  • 1: Your guess is lower than the number I picked (i.e. num < pick).
  • 0: your guess is equal to the number I picked (i.e. num == pick).

Return the number that I picked.