理解返回值-1，并且在二进制搜索中等于-1的变量

Question

我很难遍历这段应该是二进制搜索的代码。有人可以向我解释return -1和value == -1是什么意思吗？

    if high < low:
        return -1
    middle = (low + high) // 2
    if key == alist[middle]:
        return middle
    if key < alist[middle]:
        value = binary_search2(key, alist, low, middle - 1)
        if value == -1:
            return 'item is not in the list'
        return value
    else:
        value = binary_search2(key, alist, middle + 1, high)
        if value == -1:
            return 'item is not in the list'
        return value

Answer 1

-1是程序中常见的“错误”返回值。

在这种情况下，二进制搜索是递归的-函数调用自身以缩小搜索范围。返回-1是函数与较高（或较浅）的递归函数调用进行通信的方式，该递归函数调用中所搜索的项不在此列表中。

代码使用条件high < low决定是否返回-1的原因是因为high和low代表递归过程中该步骤当前搜索窗口的上下边界。如果上限小于下限，则存在逻辑错误-例如，您找不到大于4但小于3的数字-此时搜索将永远找不到所需的键，因此返回-1。

您还可以看到return value行；这样做是为了让结果（成功发现所需的密钥或失败的-1）在递归堆栈中进行[[propagated。因此，即使该函数已经多次调用自身，在第n次深度调用中，如果它返回-1，则第(n-1)次最深调用将看到此-1并将其返回到[ C0]最深层调用，然后一直执行直到到达函数的顶部调用为止，此时，启动二进制搜索的任何代码都将获悉搜索不成功。