c++ - 有人可以帮我弄清楚我在这里做错了什么吗？

Question

我正在研究 leet 代码中的一个问题，问题是:

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

我对上述问题的解决方案是:

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution 
{
    public:
        int firstBadVersion(int n) 
        {
            bool x = isBadVersion(n);
            if (x == true) 
            {
                return n;
            }
            else
            {
                return firstBadVersion(n + 1);
            }
        }
};

但是在 leet 代码上它说我有错误的解决方案。有人可以指出我正确的方向吗...

我从 leet 代码中得到的解释是:

Input: 2 versions
          1 is the first bad version.
Output: 2
Expected: 1

Answer 1

您的代码实际上会找到第一个错误版本，在传入的版本 (n) 上或之后。换句话说，这取决于您传入的内容。

我怀疑实际传入的是最高版本(尽管规范对此不明确，但这是有道理的)，这意味着您将始终提供最高版本而不是最低版本一。你最好使用类似(伪代码)的东西:

def findfirstbad(n):
    for i = 1 to n:
        if isbadversion(i):
            return i
    return sentinel # 0 or -1 or some other NA response.

在任何情况下，最小化 API 调用都需要使用二进制搜索算法，您应该对此进行研究。您目前拥有的是递归线性搜索，它不会最小化调用次数。

虽然线性搜索在每次迭代(或递归)中删除一个可能的项目，但二分搜索每次都会删除一半的剩余空间。伪代码是这样的:

def findfirstbad(n):
    # No bad version possible if no versions.

    if n < 1:
        return sentinel

    # Start pincer at ends.

    lastgood = 0
    firstbad = n

    # Continue until lastgood and firstbad are together.

    while lastgood + 1 < firstbad:
        # Find midpoint, adjust correct pincer.

        mid = (lastgood + firstbad) / 2
        if isbadversion(mid):
            firstbad = mid
        else:
            lastgood = mid

    # Ensure one last check in case there were no bad versions.

    if isbadversion(firstbad):
        return firstbad
    return sentinel

如果您借助笔和纸在脑海中运行该代码，您会发现它逐渐引入 lastgood/firstbad 索引，直到它找到第一个坏的(或发现没有坏的)。

然后一个简单的检查将决定你是否找到它，如果你找到它则返回版本。