如何在二进制搜索中选择子区间的索引？

Question

迭代二分查找算法。我以两种不同的方式编写算法。我所做的更改是 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

Answer 1

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

调用 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]: no number 10 in there!

如何在二进制搜索中选择子区间的索引？

How to choose indices of subintervals in binary search?

algorithm

binary-search

python-3.x

如何在`len(data)`和`len(data) - 1`

如何在二进制搜索中选择子区间的索引？

How to choose indices of subintervals in binary search?

algorithm

binary-search

python-3.x

如何在len(data)和len(data) - 1

如何在`len(data)`和`len(data) - 1`