Problem Statement

You are the product manager, and your team is developing a new product.
Unfortunately, one of the versions released is bad, and all the versions after it are also bad.

You have a function isBadVersion(version) that returns:

• true if the version is bad,
• false otherwise.

Your task is to find the first bad version among n versions, using the minimum number of API calls.

---

Example

Input:

n = 5, bad = 4

Versions:
1 → good
2 → good
3 → good
4 → bad
5 → bad

Output:

4

Explanation:
Version 4 is the first bad version because 4 is bad, but 3 is not.

---

Thinking About the Problem

We are told that:

• Versions before the bad one are all good.
• Versions from the bad one onwards are all bad.

This means the versions are divided into two parts:

• A sequence of false results (good versions).
• Followed by a sequence of true results (bad versions).

Whenever you encounter such a sorted pattern of true/false transition, a binary search approach is ideal.

The challenge is to efficiently find the smallest version number where the result of isBadVersion(version) changes from false to true.

---

Approach

We will apply binary search between version 1 and version n.

1. Initialize:
   • left = 1
   • right = n
2. While left < right:
   • Find the middle version:
     mid = left + (right - left) / 2
   • If isBadVersion(mid) returns true:
     • The first bad version is at mid or before mid,
       so set right = mid.
   • Else:
     • The first bad version is after mid,
       so set left = mid + 1.
3. When the loop ends, left will point to the first bad version.

---

Java Code Implementation

LeetCode provides an API called isBadVersion(version) that we can use in our solution.

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (isBadVersion(mid)) {
                // The bad version could be mid or before mid
                right = mid;
            } else {
                // The bad version is after mid
                left = mid + 1;
            }
        }

        return left; // left == right => first bad version
    }
}

---

Step-by-Step Example

Let’s walk through an example where n = 5, and version 4 is the first bad version.

left	right	mid	isBadVersion(mid)	Action	New Range
1	5	3	false	Move right	[4, 5]
4	5	4	true	Move left	[4, 4]

Now left == right == 4,
so version 4 is the first bad version.

---

Edge Cases

1. All versions are good:
   If there is no bad version, the function behavior depends on the problem’s assumption — typically, it’s guaranteed that there is at least one bad version.
2. First version is bad:
   If version 1 is bad, then the output should be 1.
3. Only one version (n = 1):
   Directly check version 1.

---

Time and Space Complexity

• Time Complexity: O(log n)
  We are dividing the search space by 2 at each step (binary search).
• Space Complexity: O(1)
  Only constant extra space is used.

---

Key Takeaways

• This is a classic binary search problem.
• Always remember:
  • If the current version is bad, move left to include it.
  • If the current version is good, move right to exclude it.
• Always use mid = left + (right - left) / 2 to avoid integer overflow.
• The final left (or right, since they become equal) gives the first bad version.

---

Intuitive Understanding

Think of the versions as a sorted array of boolean values:

[false, false, false, true, true, true]

We are trying to find the first true.
Binary search naturally fits whenever there’s a sorted pattern with a clear transition point.