Efficiently Locate the First Bad Version of a Product with Binary Search

Problem Statement

You're given a function isBadVersion(version) that returns whether a version is bad. You have a series of versions numbered from 1 to n, and your task is to find the first bad version. Once a version is bad, all the following versions are also bad.

The goal is to minimize the number of API calls to isBadVersion(version).

Example 1:

Input: n = 5, bad = 4
Output: 4

Explanation:

• isBadVersion(3) -> false

• isBadVersion(5) -> true

• isBadVersion(4) -> true

Thus, the first bad version is version 4.

Example 2:

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

Explanation: There is only one version, and it is bad, so the output is 1.

Constraints:

• 1 <= bad <= n <= 2^31 - 1

• The version numbers are ordered sequentially.

Understanding the Problem

Since the function isBadVersion(version) provides us with the information about whether a version is bad, our task is to minimize API calls while finding the exact point where the versions turn bad.

Key Observations:

1. If a version is bad, all the versions after it will also be bad.

2. If a version is not bad, then all previous versions are also not bad.

3. We need to locate the first bad version, so the solution must find this "boundary" efficiently.

Optimal Approach: Binary Search

The binary search algorithm is ideal for this problem because we are essentially searching for a point in a sorted sequence where the property changes from false (good) to true (bad). With binary search, we can reduce the time complexity to O(log n).

Approach Breakdown:

1. Initialize Pointers: Start with two pointers, left and right. left starts at 1 (first version), and right starts at n (last version).

2. Binary Search Loop:

   • Compute the midpoint, mid, between left and right.

   • Call isBadVersion(mid):

     • If mid is bad, check if it is the first bad version by verifying whether mid-1 is not bad. If it is, return mid.

     • Otherwise, move the right pointer to mid - 1 (since all versions after mid are bad).

     • If mid is not bad, move the left pointer to mid + 1 (since all versions before mid are good).

3. Return Result: When the pointers converge, the first bad version is found.

Code Implementation in TypeScript:

// The isBadVersion API is provided, we simulate it here for understanding.
// function isBadVersion(version: number): boolean { /* ... */ }

var solution = function (isBadVersion: any) {
    return function (n: number): number {
        let left = 1;
        let right = n;

        while (left <= right) {
            let mid = Math.floor(left + (right - left) / 2);
            if (isBadVersion(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    };
};

How It Works:

1. We initialize left to 1 and right to n, representing the range of versions.

2. We compute the midpoint and check if it's bad using isBadVersion(mid).

3. If it's bad, we check if it's the first bad version. If so, we return the version number. If not, we adjust the search range to the left half by moving right.

4. If it's not bad, we adjust the search range to the right half by moving left.

Time Complexity:

• Time Complexity: O(log n) because we are using binary search to reduce the search space in half each time.

• Space Complexity: O(1) since we only use a few variables for our pointers and calculations.

Comment if I have committed any mistake. Let's connect on my socials. I am always open for new opportunities , if I am free :P

Linkedin| Twitter | ShowwCase