First Bad Version Problem (C++, Java, Python)

 

Binary Search is one of the important topics that are asked in interviews. The basic idea is to check the middle value, and you decide to go either right or left based on this. The binary search helps you to reduce your time complexity significantly. This article will discuss the problem “First Bad Version” based on Binary Tree, which is also part of leetcode.

First Bad Version Problem Explained

In the First Bad Version problem, you are given a number that represents the total number of versions of a product. Unfortunately, your latest version has some defects, causing all subsequent versions to be defective. Your task is to find the first defective version. You are provided with an API, bool isBadVersion(n), which indicates whether a given version is defective or not. Find the first defective version using the provided API while minimizing the number of calls made to it.

Here is how it works:

Input: n = 5, bad = 3.

Output: t=2 ->good

             t=3 ->bad

             t=4 ->bad

             t=5 ->good.

The basic approach to the given problem is to start from the first index and call the API for each of them till it returns that the given version is bad. Return this as the first bad version.

Let’s understand this approach step by step:

• Start from index 1 and call the API isBadVersion.
• If you get true as a result return this index as the first Badversion
• Otherwise, move to the next index and repeat the same process till you reach the bad version.

The time complexity for the above approach is O(n) where n is the total number of versions given to you as we are going to each index and at worst the bad version may be the last so the worst time complexity is O(n). The space complexity is O(1) as we are not using any extra space.

Binary Search Approach

In the above approach, it took O(n) time, which can be reduced if we use binary search. As we know, all the versions after the first bad version are bad. Therefore, if we find any bad version, the first bad version is either at this index or before it, but not after. Similarly, if we determine that this index is not a bad one, we need to search after it, not before it. Let’s examine this approach:

• Create two variables, first and last which store the starting and ending index respectively.
• Now keep on iterating till the first index is less than the last index.
• Check if the middle element of the first and last index is bad or not with the help of API.
• If it is the bad version update the last index to the middle index.
• If not, update the first index to the mid+1 index.

• If at any point the first and last index become equal return the first index as the first bad version as an answer.

Let’s examine the code for the above process.

C++ Code

Here is the C++ implementation of the Binary Search approach:

class Solution {

public:

    int firstBadVersion(int n) {

        // binary search approach

        // first represents the starting index and last represents the last index.

        long long int first = 1, last = n;

        while(first<last){

            long long int mid = (first+last)/2;

            // if isBadVersion return true at mid means the mid value is bad => all the values after that are also bad.

            if(isBadVersion(mid)) last = mid;

            else first = mid+1;

        }

        return first;

    }

};

Java Code

You can program it with Java also:

public class Solution {

    public int firstBadVersion(int n) {

        // Binary search approach

        // First represents the starting index and last represents the last index.

        long first = 1, last = n;

        while (first < last) {

            long mid = (first + last) / 2;

            // If isBadVersion returns true at mid means the mid value is bad => all the values after that are also bad.

            if (isBadVersion(mid)) {

                last = mid;

            } else {

                first = mid + 1;

            }

        }

        return (int) first;

    }

}

Python Code

We can do this in Python as well:

class Solution:

    def firstBadVersion(self, n: int) -> int:

        # Binary search approach

        # First represents the starting index and last represent the last index.

        first = 1

        last = n

        while first < last:

            mid = (first + last) // 2

            # If isBadVersion returns true at mid means the mid value is bad => all the values after that are also bad.

            if self.isBadVersion(mid):

                last = mid

            else:

                first = mid + 1

        return first

Complexity Analysis

The time complexity for solving the First Bad Version problem is reduced to O(log(n)) due to binary search. As we are just iterating loops for at most log(n) times. The space complexity will again be 0.

Here is the comparison of both methods:

Conclusion

In this article, we have seen how we can use binary search to solve the leetcode problem of the First Bad Version. This helps us reduce our time complexity from O(n) to O(log(n)). Binary search has many more applications.