10.FirstBadVersion.md

🐛 First Bad Version

📄 Problem Statement

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.

You have n versions numbered from 1 to n. You want to find out the first bad version—the smallest version number for which isBadVersion(version) returns true.

Implement a function firstBadVersion(n) that returns this first bad version. You may call the provided API bool isBadVersion(int version).

---

💡 Intuition

• Versions are linearly ordered and “good” versions (false) come before the first bad version, and all versions after it are bad (true).
• We’re looking for the leftmost true in a boolean array of length n.
• Binary search finds that boundary in O(log n) by repeatedly halving the search space.

---

🐢 Brute‑Force Approach

• Check versions 1, 2, 3, … until you find the first bad one.

int firstBadVersionBrute(int n) {
    for (int v = 1; v <= n; ++v) {
        if (isBadVersion(v)) 
            return v;
    }
    return -1; // should never happen if at least one is bad
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Too slow if n up to 10⁹.

---

🚀 Optimal Approach: Binary Search

int firstBadVersion(int n) {
    int low = 1, high = n;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (isBadVersion(mid)) {
            // mid might be first bad, but search left half
            high = mid - 1;
        } else {
            // mid is good, so first bad is to the right
            low = mid + 1;
        }
    }
    // low is the smallest index such that isBadVersion(low) == true
    return low;
}

• Key: On true, move high = mid - 1; on false, low = mid + 1.

• After the loop, low points to the first true.

• Time Complexity: O(log n)

• Space Complexity: O(1)

---

✅ Full Code with Simulation and main()

#include <bits/stdc++.h>
using namespace std;

// Simulation of the API; we store the first bad version:
int FIRST_BAD;

// Mocked API:
bool isBadVersion(int version) {
    return version >= FIRST_BAD;
}

/**
 * Finds the first bad version in [1..n] using binary search.
 */
int firstBadVersion(int n) {
    int low = 1, high = n;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (isBadVersion(mid)) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    // Read total number of versions and the first bad version index
    // Format: n FIRST_BAD
    cin >> n >> FIRST_BAD;

    int result = firstBadVersion(n);
    cout << result << "\n";
    return 0;
}

---

🧮 Complexity Analysis

Operation	Time Complexity	Space Complexity
Binary search loop	O(log n)	O(1)
API calls	up to O(log n)	—
Overall	O(log n)	O(1)

---

🎯 Tips & Tricks

• Overflow‑safe mid: use mid = low + (high−low)/2 instead of (low+high)/2.
• Always verify loop invariant: after each iteration, the first bad version remains within [low…high+1].
• At the end, low is the smallest index where isBadVersion(low) == true.

---

🔄 Variations

1. First/Last occurrence of any boolean predicate over an indexed range.
2. Minimum capacity / maximum threshold problems (search on a monotonic predicate).
3. Search in rotated array with a custom boundary condition.

---

❓ FAQs

Q1. Why return low instead of high + 1?

After the loop, high points to the last false (good), so high + 1 == low is the first true.

Q2. What if no version is bad?

Problem guarantees at least one bad. Otherwise you’d check low <= n and return -1 if low > n.

Q3. Can the API calls be expensive?

Minimize them via binary search (~30 calls for n up to 10⁹).

Q4. How to handle 1‑based vs 0‑based versions?

Adjust initial low/high accordingly; here we assume 1‑based.

---