如何在 Python 中高效地实现二分查找来检查项目是否存在？

Python中的二分搜索（折半查找）

Python提供了实现二分搜索（也称为折半查找）的库函数，用于在排序列表或元组中查找项。不过，这些函数在项未找到时仍然会返回一个位置。

为了解决这个问题并仅检测项是否存在，一种方法是使用bisect.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

此函数使用bisect_left()函数查找插入位置，该位置指示目标项存在时的位置，或指示其不在时超出范围的位置。通过检查该位置处的项是否与目标项相等，可以确定目标项是否存在。

以上是如何在 Python 中高效地实现二分查找来检查项目是否存在？的详细内容。更多信息请关注PHP中文网其他相关文章！