如何使用 Python 中的二分搜索有效地检查排序列表中的项目是否存在？

使用显式项目存在检查的 Python 中的二分搜索（二分）

Python bisect 模块提供执行二分搜索的函数，例如 bisect_left和 bisect_right。但是，即使正在搜索的项目不存在于列表中，这些函数也会返回一个位置。对于仅需要某个项目存在或不存在的情况，需要更明确的检查。

一种方法是使用 bisect_left 并验证返回位置的项目是否与目标匹配。然而，这种方法引入了额外的复杂性，例如对目标大于列表中最大元素的情况进行边界检查。

更简单、更直接的解决方案是实现一个自定义的二分搜索函数，该函数显式检查在返回结果之前检查该项目是否存在。下面是一个示例：

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):
    if hi is None: hi = len(a)
    pos = bisect_left(a, x, lo, hi)                  # find insertion position
    return pos if pos != hi and a[pos] == x else -1  # don't walk off the end

此函数采用排序列表 a、目标值 x 以及可选的搜索下限和上限。它使用 bisect_left 查找 x 的插入点，然后检查该位置的项目是否与目标匹配。如果找到匹配项，该函数将返回位置；否则，它返回 -1 来指示该项目不存在。

通过合并此显式检查，您可以有效地确定排序列表中是否存在某个项目，而不会引入不必要的开销或限制。

以上是如何使用 Python 中的二分搜索有效地检查排序列表中的项目是否存在？的详细内容。更多信息请关注PHP中文网其他相关文章！