This is the 13th day of my participation in the Genwen Challenge

Topic describes

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

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 tell if version failed in unit tests by calling the bool isBadVersion(version) interface. Implement a function to find the first incorrect version. You should minimize the number of calls to the API.

Example:

Given n = 5, and version = 4 is the first incorrect version. Call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true so, 4 is the version with the first error.Copy the code

Their thinking

Because the title requires you to minimize the number of times you call the check interface, you should not call the check interface for every version, but rather minimize the number of times you call the check interface.

Note that when a version is the correct version, all previous versions are the correct version; If a version is an incorrect version, all subsequent versions are incorrect versions. We can use this property for binary search.

Specifically, the left and right boundaries are initialized to 111 and NNN, respectively, where NNN is the given number of versions. After setting the left and right boundaries, each time we find the intermediate version based on the left and right boundaries and check if it is the correct version. If the version is correct, then the first incorrect version must be to the right of the version. We indent the left margin; Otherwise, the first incorrect version must be to the left of that version and to the left of that version. We indent the right margin.

In this way, we can tighten the boundary every time we make a judgment, and each time the distance between the two boundaries will be half of the original, so we only need to tighten order (log n) times at most.

code

C + + code

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) { // loop until the left and right endpoints of the interval are the same
            int mid = left + (right - left) / 2; // Prevent overflow during calculation
            if (isBadVersion(mid)) {
                right = mid; // The answer is in the interval [left, mid]
            } else {
                left = mid + 1; // The answer is in the interval [mid+1, right]}}// Left == right
        returnleft; }};Copy the code