449. Find First Bad Version

You are a product manager with n versions [1..n]. A bad version causes all subsequent versions to be bad. Given isBadVersion(version) API (simulated here by the parameter bad — all versions >= bad are bad), find the first bad version. Minimize API calls.

Input: Integer n (total versions) and integer bad (first bad version, 1 <= bad <= n).

Output: The first bad version number.

Examples

Input: 5, 4
Output: 4
Explanation: isBadVersion(3)=false, isBadVersion(4)=true → first bad is 4.

Input: 1, 1
Output: 1
Explanation: Only one version and it's bad.

Input: 10, 1
Output: 1
Explanation: All versions are bad; first bad is 1.

Constraints

• 1 <= bad <= n <= 2^31 - 1

Asked by