python - 二进制搜索以在 Python 中找到可能的最高值

Question

我有一个非常大的数字（20 位数字），我需要找到它。所以在 0 到 99999999999999999999 之间的范围内。

我可以检查数字是否大于或小于猜测的数字，例如：

is_smaller(12341234123412341234)
# True
is_smaller(98769876987698769876)
# False

但是，该函数的is_smaller工作原理尚不清楚，但数字的值是恒定的。

这可以通过二进制搜索来解决吗 - 我不太确定如何实现这一点，因为我只知道数字是否更小/更大。我遇到的大多数二进制搜索实现都使用它在数组中查找给定数字，这对我不起作用，因为该数字是未知的。

在这种情况下如何使用二进制搜索，或者另一种方法更适合？

目标是找到仍然返回的最高可能True值is_smaller。

---

编辑：我无法判断数字是否更大，所以我没有is_bigger功能。因此，在较小的范围内（例如 0 到 10），如果感兴趣的数量是6，我拥有的函数将返回：

[...]
is_smaller(4)
# True
is_smaller(5)
# True
is_smaller(6)
# True
is_smaller(7)
# False
is_smaller(8)
# False

我不得不承认问题中的函数名称选择得非常糟糕。

标签： pythonnumbersbinary-search-treebinary-search

Answer 1

如果某物既不大于也不小于您要查找的数字，那就是您要查找的数字。

def is_answer(n):
    return not is_smaller(n) and not is_larger(n)

现在你可以使用标准的二分查找了；只需替换看起来像的条件

if x == search_term:
if x < search_term:
if x > search_term:

和

if is_answer(x):
if is_smaller(x):
if is_larger(x):

分别。如果你想为你的二分搜索使用<=or>=运算符，你可以从这些构建块中自己构建它。