Your team ships numbered versions of an app: version 1, version 2, and so on up to version n. Today you find that the newest version fails the quality check. Each version is built on the one before it, so once a version is bad, every later version is bad too.
You want to find the first bad version, the one that started the problem. You are given a function bool isBadVersion(version) that tells you whether a version is bad. Find the first bad version and call that function as few times as you can.
How this judge runs it. The judge picks the first bad version for each test, but it does not tell you. Your function receives only n. To check a version, call isBadVersion(version). The judge provides this function for you, and it returns true when that version is bad. (The Input line of each example also shows bad, the number the judge chose, so that you can follow the example. Your function does not receive it.) Return the first bad version.
The judge counts your calls to isBadVersion. If you call it too many times, the test fails with an error. The limit is 2 * b + 4, where b is the number of digits of n when you write it in binary. For n = 100 the limit is 18 calls, and for n = 2147483647 it is 66 calls. Checking the versions one by one needs far more calls than this, so use binary search.
Examples
Example 1:
Input: n = 10, bad = 7
Output: 7
Explanation: Versions 1 to 6 are good and versions 7 to 10 are bad. Check version 5 (good), then 8 (bad), then 6 (good), then 7 (bad). The first bad one is 7.
Example 2:
Input: n = 1, bad = 1
Output: 1
Explanation: There is only one version, and it is bad.
Example 3:
Input: n = 100, bad = 64
Output: 64
Explanation: Versions 64 to 100 are bad, so the first bad version is 64.