时间戳

首页 > 解决方案 > 如何在二分搜索中选择子区间的索引？

python-3.x - 如何在二分搜索中选择子区间的索引？

问题描述

迭代二分查找算法。我以两种不同的方式编写算法。我所做的更改是 high = len(data) 和 high = len(data) -1 。在这两种情况下，算法都运行良好。但是在大多数站点中，它们显示 high = len(data) -1 是正确的方法。所以使用 -1 更好，为什么？

第一个代码）

def iterative_binary_search(data, target):
    low = 0
    high = len(data)               # this line is where I need help
    while low <= high:
        mid = (low + high) // 2
        if target == data[mid]:
            return True
        elif target < data[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return False

第二个代码）

def iterative_binary_search(data, target):
    low = 0
    high = len(data) -1           # this line is where I need help
    while low <= high:
        mid = (low + high) // 2
        if target == data[mid]:
            return True
        elif target < data[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return False

标签： python-3.xalgorithmbinary-search

解决方案

其中一个代码运行不正常。

用调用ibs1第一个，用high=len(data)调用ibs2第二个high = len(data)-1，我得到：

>>> haystack = [0,1,2,3,4,5,6,7,8,9]
>>> ibs2(haystack, 11)
False
>>> ibs1(haystack, 11)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 6, in ibs1
IndexError: list index out of range

如何在len(data)和之间做出决定len(data) - 1

你需要决定什么low和high代表什么，并在你的脑海中非常清楚。当low=3和high=6，是什么意思？这是否意味着我们在列表索引 3 和 6 之间进行搜索？还是排除在外？这由你决定。如果包含它，那么您应该使用high = len(data) - 1，因为这是数组最高元素的索引。如果它被排除在外，您应该使用high = len(data)，因为它是数组中最高元素的索引之后的一个。

两个决定都很好。但是这个决定必须反映在其余代码的逻辑中。

因此，此代码也是正确的：

def ibs3(haystack, needle):
  low = 0
  high = len(haystack)
  while low < high:
    mid = (low + high) // 2
    if needle == haystack[mid]:
      return True
    elif needle < haystack[mid]:
      high = mid
    else:
      low = mid + 1
  return False

请注意，在 python 中，约定通常是包含low和排除high. 例如，print(list(range(7, 10)))打印[7, 8, 9]：那里没有数字 10！

推荐阅读