This is the 16th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Topic Description:

278. First incorrect version – LeetCode (leetcode-cn.com)

You are a product manager and are currently leading a team to develop a new product. Unfortunately, the latest version of your product does not pass the quality test. Since each version is based on the previous version, all versions after the wrong version are wrong.

Suppose you have N versions [1, 2… n] and you want to find the first incorrect version that causes all subsequent versions to fail.

You can determine if the version number is wrong in the unit test by calling the bool isBadVersion(Version) interface. Implement a function to find the first incorrect version. You should try to minimize the number of calls to the API.

Example 1:

Input: n = 5, bad = 4 Call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true so 4 is the first incorrect version.Copy the code

Example 2:

Input: n = 1, bad = 1 Output: 1Copy the code

Tip:


  • 1 < = b a d < = n < = 2 3 1   – 1 1 <= bad <= n <= 2^31 – 1

Thought analysis

Binary search

Since the question asks to minimize the number of calls to the check interface, you should not call the check interface for each version, but rather minimize the number of calls to the check interface.

Because each version is based on the previous version, all versions after the wrong version are wrong.

Conversely, we can infer that when one version is the correct version, all previous versions are the correct version.

It’s easy to think of a dichotomy.

The specific code process will not write in detail, done several problems. Go straight to the code.

AC code

/* The isBadVersion API is defined in the parent class VersionControl. def isBadVersion(version: Int): Boolean = {} */

class Solution: VersionControl() {
    override fun firstBadVersion(n: Int) : Int {
        var left = 1
        var right = n
        while(left < right){
            var mid = left + (right - left)/2
            if(isBadVersion(mid)){
                right = mid
            }
            else{
                left = mid + 1}}return left
    }
}
Copy the code

conclusion

It’s a very clear idea, it’s a dichotomy, but the main thing is to pay attention to the boundaries of the dichotomy.

reference

First wrong version – First wrong version – LeetCode (leetcode-cn.com)