First Bad Version

## 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. Suppose you have `n` versions `[1, 2, ..., n]` and you want to find out the first bad one, which causes all the following ones to be bad. You have access to an API `isBadVersion(version)` which returns whether `version` is bad. Implement a function to find the first bad version. You should **minimize the number of API calls**. For testing, the function signature is `firstBadVersion(n, bad)` where `bad` is the first bad version threshold — all versions `>= bad` are considered bad. ## Examples **Example 1:** ``` Input: n = 5, bad = 4 Output: 4 Explanation: Versions 1, 2, 3 are good. Version 4 is the first bad version. isBadVersion(3) -> False isBadVersion(5) -> True isBadVersion(4) -> True First bad version is 4. ``` **Example 2:** ``` Input: n = 1, bad = 1 Output: 1 ``` ## Hints - This is a classic binary search problem. - Search in the range `[1, n]`. When `isBadVersion(mid)` is True, the answer is at most `mid`. When it is False, the answer is in `(mid, n]`. - Use integer midpoint `mid = left + (right - left) // 2` to avoid overflow.