First Bad Version

Concept

LeetCode #278.
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. You have n versions [1, 2, ..., n] and you want to find out the first bad one. You are given an API isBadVersion(version) which returns a boolean.

This is a classic variation of Binary Search.
Instead of searching for a specific number in an array, you are searching for the Boundary between false and true.

[Good, Good, Good, Bad, Bad, Bad]
(false, false, false, true, true, true)

You need to find the exact index of the very first true.

The Boundary Strategy

If we check a version and isBadVersion(mid) is false, we know the first bad version MUST be somewhere to the right. We aggressively move our left boundary: left = mid + 1.

If we check a version and isBadVersion(mid) is true, we know this version is bad. BUT, we don’t know if it is the first bad version! The first bad version might be sitting immediately to its left.
Because the current mid might physically be the correct answer, we cannot eliminate it. We move our right boundary to right = mid. (Notice the lack of - 1!).

Implementation

Because we use right = mid, we must change the while loop to while (left < right). If we kept <=, the loop would infinite loop when left and right collide on the target!

// isBadVersion is an API provided by LeetCode
const solution = function(isBadVersion: any) {

    return function(n: number): number {
        // Versions are 1-indexed
        let left = 1;
        let right = n;
        
        // Use < so it terminates the exact moment Left and Right collide!
        while (left < right) {
            const mid = left + Math.floor((right - left) / 2);
            
            if (isBadVersion(mid) === true) {
                // This version is bad. But is it the FIRST bad one?
                // The answer is either this exact mid, or somewhere to its left.
                // We keep mid in the search space!
                right = mid;
            } else {
                // This version is good. The first bad one MUST be to the right.
                // We aggressively discard mid because it's useless.
                left = mid + 1;
            }
        }
        
        // When the loop breaks, Left and Right have collapsed onto the exact same spot.
        // That spot is mathematically guaranteed to be the boundary.
        return left;
    };
};

Binary Search on Answer

This exact template (while (left < right)) is universally used for “Binary Search on Answer” problems (like Koko Eating Bananas or Capacity To Ship Packages Within D Days).

In these advanced problems, you are trying to find the Minimum Capacity (the Boundary) that allows you to complete a task.
You write a custom isValid(capacity) helper function.
You set left = 1 and right = absolute_max_possible.
You binary search the integers. If a capacity works, you try a smaller one (right = mid). If it fails, you are forced to use a bigger one (left = mid + 1).

Interview Questions

Q: In the First Bad Version problem, if isBadVersion(mid) is true, why don’t we just explicitly check isBadVersion(mid - 1) to see if it is the boundary, so we can return instantly?
A: You can! Adding if (isBadVersion(mid) === true && isBadVersion(mid - 1) === false) return mid; will indeed short-circuit the loop and find the exact answer early. However, interviewers often discourage this because it calls the expensive API function twice per iteration. The mathematical contraction approach (right = mid) is considered more elegant and robust because it naturally isolates the boundary using only one API call per loop.