在二进制搜索中，计算机如何选择中点以及何时仅剩两个元素

Question

我已经阅读了一些关于此问题的stackoverflow问题和其他博客。

他们大多数解释使用以下方法选择中点：

1. low + (high - low)/2
2. (low + high)/2, round down to integer.

来自Deciding mid in binary search和https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-search

它们都没有道理。

说我有一个列表，形式

lst = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

使用1.中点= 46.5并使用2.中点= 50.5，向下舍入为50。

两个中点都不在我的列表中。

此外，当只有2个元素时，它将选择哪个元素作为中点？

Answer 1

low和high变量不引用列表或数组的元素。它们引用列表或数组的索引。因此，中间元素将不会由low + (high - low)/2或(low + high)/2（向下舍入为整数）给出，而由lst[low + (high - low)/2]或lst[(low + high)/2]

给出

Answer 2

二进制搜索的低/高是指ndexe，而不是数组值。因此，在您的情况下，中间的[[index为（0 + 9）/ 2 = 4。

在长度为2的情况下，您将获得中间索引0，右侧部分将具有一个元素，左侧为空（或者，如果不单独处理mid，则将仅包含第0个元素。）>

Answer 3

1. [low和high是指列表的索引，而不是它们的值

Answer 4

您正在计算系列的平均值，而不是中点。