我已经阅读了一些关于这个问题的 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.midpoint = 46.5 并使用 2.midpoint = 50.5,四舍五入为 50。
两个中点都不在我的列表中。
而且当只有2个元素时,它会选择哪一个作为中点?
最佳答案
low
和high
变量不引用列表或数组的元素。它们引用列表或数组的索引。因此,中间元素不会由以下方式给出:low + (high - low)/2
或 (low + high)/2
(向下舍入为整数),而是通过 lst[low + (high - low)/2]
或 lst[(low + high)/2]
关于python - 在二分查找中,计算机如何选择中点以及何时只剩下两个元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59691836/