278. First Bad Version

EasyBinary SearchInteractive
Leetcode Link

Problem Description

You are a product manager overseeing the development of a new product, which unfortunately has some versions failing the quality check. Versions of this product are built sequentially where each version builds upon the previous one. If any version is discovered to be faulty, all subsequent versions will inherit this fault.

Your task is to efficiently determine the first version where the defect was introduced, given that subsequent versions will be defective as well. You have n versions labeled from 1 to n. To assist in identifying the defective version, you have access to a provided API function isBadVersion(version) that will return true if the version is bad, and false otherwise.

The goal is to minimize the number of API calls you make to isBadVersion.

Intuition

To solve this problem, a binary search algorithm is an ideal approach. Binary search is applied because we know the versions are ordered from good to bad and the first bad version triggers all the following versions to be bad as well. This creates a sorted pattern of good and bad versions, which is perfect for binary search.

Initially, we know the right boundary (right) of our search space is n (the last version) and the left boundary (left) is 1 (the first version). To minimize the calls to the API, we avoid searching versions sequentially. Instead, we calculate the middle point (mid) of the current search space and use the isBadVersion API to check if mid is a bad version.

If mid is bad, we know that the first bad version must be at mid or before mid, so we set right to mid. If not, we know that the first bad version must be after mid, so we update left to be mid + 1. This halves the search space with each iteration.

Repeatedly narrowing the search space like this leads us to converge on the first bad version without checking every version. The loop terminates when left and right meet, which is when we have found the first bad version. By utilizing this method, the number of calls we make to the API is reduced to O(log n), which is the time complexity of a binary search.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

In a binary min heap, the minimum element can be found in:

Solution Approach

The solution implements a classic binary search strategy to find the first bad version. This method significantly reduces the time complexity from O(n) to O(log n). Let's walk through the implementation of the solution:

  1. We start by initializing two pointers, left and right. left starts at 1, which represents the first version, and right starts at n, which represents the last version. They mark the boundaries of our search space.

  2. We enter a while loop that will continue running as long as left is less than right. Inside this loop, we will repeatedly narrow down our search space by inspecting the midpoint of left and right.

  3. To calculate the midpoint, we use the expression (left + right) >> 1, which is equivalent to (left + right) / 2 but faster computationally as it involves bit-shifting to the right by one bit to do integer division by two. We assign this value to the variable mid.

  4. The isBadVersion(mid) call tells us whether the midpoint version is bad. If it is, we know the target bad version must be less than or equal to mid. So, we set right to mid, indicating our search space has shifted to the left half from left to mid.

  5. Conversely, if isBadVersion(mid) returns false, it means that the first bad version is somewhere after mid. Hence, we set left to mid + 1, indicating our search space has shifted to the right half excluding mid.

  6. The loop continues, and with each iteration, the range [left, right] narrows down until left equals right. At this point, left (or equivalently right) points to the first bad version.

With the binary search pattern applied, we not only find the correct answer but also optimize performance by making the least number of calls necessary to isBadVersion, satisfying the problem's constraint to minimize API calls. Once the loop finishes, we return left as it will be the index of the first bad version.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Example Walkthrough

Suppose we have 5 versions of a product and we know that one of the middle versions introduced a defect. Our isBadVersion API functions as follows for these 5 versions:

  • isBadVersion(1) returns false
  • isBadVersion(2) returns false
  • isBadVersion(3) returns true
  • isBadVersion(4) returns true
  • isBadVersion(5) returns true

Using the binary search approach, we start with left = 1 and right = 5. We perform the following steps to identify the first bad version:

  1. First, take the midpoint of left (1) and right (5). The midpoint mid is calculated as (1 + 5) >> 1 which equates to 3.

  2. We check isBadVersion(3) and it returns true. Because mid is bad, we know all versions after 3 are also bad. So, we set right to mid, changing our range from [1, 5] to [1, 3].

  3. Next, we recalculate the midpoint of the new range. With left still at 1 and right at 3, the new mid is (1 + 3) >> 1, which equals 2.

  4. We call isBadVersion(2) and it returns false. Now we know the first bad version must be greater than mid. So we update left to mid + 1, changing our range from [1, 3] to [3, 3].

  5. Since left and right meet and the loop terminates, we conclude that the first bad version is 3.

By following this example, the approach narrows down the search space efficiently and we find the first bad version which is 3, with just two API calls to isBadVersion instead of five, which would have been the case if we had checked each version sequentially. This demonstrates the effectiveness of the binary search technique.

Solution Implementation

1# Assume the isBadVersion API is already defined.
2# @param version: int => An integer representing the version
3# @return bool => True if the version is bad, False otherwise
4# def isBadVersion(version):
5
6
7class Solution:
8    def firstBadVersion(self, n: int) -> int:
9        """
10        Utilize binary search to find the first bad version out of 'n' versions.
11        If a bad version is found, then all subsequent versions are also bad.
12
13        :type n: int The total number of versions to check.
14        :rtype: int The first bad version number.
15        """
16        # Initialize the search space
17        left, right = 1, n
18        # Loop until the search space is reduced to one element
19        while left < right:
20            # Calculate the middle point to divide the search space
21            mid = left + (right - left) // 2
22            # If mid is a bad version, the first bad version is in the left half
23            if isBadVersion(mid):
24                right = mid  # Narrow the search to the left half
25            else:
26                left = mid + 1  # Narrow the search to the right half
27      
28        # At this point, left is the first bad version
29        return left
30
1public class Solution extends VersionControl {
2    /**
3     * Finds the first version that is bad.
4     * 
5     * @param n Total number of versions.
6     * @return The first bad version number.
7     */
8    public int firstBadVersion(int n) {
9        // Initialize pointers for the range start and end.
10        int start = 1;
11        int end = n;
12      
13        // Continue searching while the range has more than one version.
14        while (start < end) {
15            // Calculate the middle version of the current range.
16            // Using unsigned right shift operator to avoid integer overflow.
17            int mid = start + (end - start) / 2;
18          
19            // Check if the middle version is bad.
20            if (isBadVersion(mid)) {
21                // If the middle version is bad, the first bad version 
22                // is before it or it is the first bad version itself.
23                end = mid;
24            } else {
25                // If the middle version is good, the first bad version
26                // must be after it.
27                start = mid + 1;
28            }
29        }
30      
31        // At this point, start == end and it is the first bad version.
32        return start;
33    }
34}
35
1// The API isBadVersion is defined for you.
2// bool isBadVersion(int version);
3
4class Solution {
5public:
6    // Function to find the first bad version in a sequence of versions
7    int firstBadVersion(int n) {
8        int left = 1;           // Initialize the left boundary of the search range
9        int right = n;          // Initialize the right boundary of the search range
10      
11        // Perform a binary search to narrow down the first bad version
12        while (left < right) {  
13            // Use bitwise shift to avoid the potential overflow of (left + right)
14            int mid = left + ((right - left) >> 1);
15          
16            // Check if the middle version is bad
17            if (isBadVersion(mid)) {
18                // If it is bad, we know that the first bad version must be at or before 'mid'
19                right = mid;    // Reset the right boundary to 'mid'
20            } else {
21                // If it is not bad, the first bad version must be after 'mid'
22                left = mid + 1; // Reset the left boundary to one after 'mid'
23            }
24        }
25      
26        // At the end of the loop, 'left' will be the first bad version
27        return left;
28    }
29};
30
1/**
2  * The `isBadVersion` function is a predicate that determines whether
3  * a given software version is bad. The actual implementation is unspecified.
4  *
5  * @param version - The version number to check.
6  * @returns `true` if the specified version is bad, otherwise `false`.
7  */
8type IsBadVersion = (version: number) => boolean;
9
10/**
11  * This function is a higher-order function that takes in the `isBadVersion` function
12  * and returns a nested function that can be used to find the first bad version.
13  *
14  * @param isBadVersion - A function to determine whether a given version is bad.
15  * @returns A function that accepts the total number of versions `n` and returns the
16  * first bad version found.
17  */
18const solution = (isBadVersion: IsBadVersion): ((n: number) => number) => {
19  /**
20   * This inner function uses binary search to efficiently find the first bad version 
21   * within the total number of versions `n`. 
22   *
23   * @param n - The total number of versions to search through.
24   * @returns The first bad version number within the total versions.
25   */
26  return (n: number): number => {
27    let left: number = 1;
28    let right: number = n;
29    while (left < right) {
30      // Use Math.floor to ensure the result is an integer after the division.
31      const midpoint: number = left + Math.floor((right - left) / 2);
32      if (isBadVersion(midpoint)) {
33        right = midpoint;
34      } else {
35        left = midpoint + 1;
36      }
37    }
38    // At this point, 'left' is the first bad version.
39    return left;
40  };
41};
42
Not Sure What to Study? Take the 2-min Quiz：

In a binary min heap, the minimum element can be found in:

Time and Space Complexity

The given code snippet uses a binary search algorithm to find the first bad version among n versions. The binary search successively divides the range of the search in half, narrowing down on the first bad version.

Time Complexity

The time complexity of this algorithm is O(log n). This is because with each comparison, it effectively halves the search space, which is a characteristic of binary search. As such, the number of comparisons needed to find the target is proportional to the logarithm of the total number of versions n.

Space Complexity

The space complexity of this algorithm is O(1). This is because it uses a fixed amount of space; only two variables left and right are used to keep track of the search space, and the mid variable is used for the computations. No additional space is dependent on the input size n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer technique does Quick Sort use?

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫