This is the 27th day of my participation in the More Text Challenge. For more details, see more text Challenge

The first incorrect version (Question Number 278)

The title

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:

Given n =5, and version =4Is the first incorrect version. Call isBadVersion (3) - >falseCall isBadVersion (5) - >trueCall isBadVersion (4) - >trueSo,4Is the first incorrect version.Copy the code

link

Leetcode-cn.com/problems/fi…

explain

This one, this is a classic dichotomy.

The main thing is that the topic has a requirement:

You should try to minimize the number of calls to the API.

The time for binary is order logn, and the time for regular traversal is order n, so obviously we’re going to solve this problem in two.

Of course, a normal loop can also solve the problem, and the amount of code is minimal, but the performance is poor.

I know this is a dichotomy, but this dichotomy is a little bit different from the usual dichotomy, boundary problem.

The code for regular dichotomies basically looks like this 👇 :

var mid = ~~((left + right) / 2)
if (isBadVersion(mid)) {
  right = mid - 1
} else {
  left = mid + 1
}
Copy the code

The key is these two lines 👇 :

right = mid - 1
left = mid + 1
Copy the code

In this case, if you write it like this, you have a problem, sometimes you miss the right answer, and the left position might be before the right answer, or it might be the right answer.

Why is that?

Let’s look at the problem, the problem requires that the correct version number is followed by the wrong version number, so the interval is the logic 👇 :

  1. If mid is the correct version

    So the first error version range is in [mid + 1, right]

  2. If mid is an incorrect version

    According to classical dichotomy logic, the first error version number interval is in [left, mid-1]

    Because the wrong version number must be on the right side, and mid is the wrong version, then if the interval value is [left, mid-1], then mid-1 may become the correct version number, if continue to binary, the left can only be mid-1, But the first incorrect version number is MID, so the final result will be incorrect.

    So in case mid is the wrong first version number, the interval should be [left, mid].

So the dichotomous logic here would be 👇 :

var mid = ~~((left + right) / 2)
if (isBadVersion(mid)) {
  right = mid
} else {
  left = mid + 1
}
Copy the code

Your own answer (violence)

var solution1 = function(isBadVersion) {
  return function(n) {
    for (let i = 1; i <= n; i++) {
      if (isBadVersion(i)) return i
    }
  };
};
Copy the code

Classic violence, nothing to say, very simple, but poor performance.

Your own answer (two points)

The logic of dichotomies has been explained in the explanation section, so take a look at the code 👇 :

var solution = function(isBadVersion) {
  return function(n) {
    var left = 1
        right = n
    while (left < right) {
      var mid = ~~((left + right) / 2)
      if (isBadVersion(mid)) {
        right = mid
      } else {
        left = mid + 1}}return left
  };
};
Copy the code

Mainly on the assignment of the right margin, remember to consider the mid is the wrong version of the case.

Not much else. Classic two.

A better way

There is no




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ