algorithm - 为什么二进制搜索算法使用 floor 而不是 ceiling - 不在半开放范围内

Question

例如，当我们有一个索引从 0 到 n 的数组时。当我在计算中间索引时使用下限或上限使用二进制搜索时，我得到了相同的输出。

int middle = ceiling ((left+right)/2);

在天花板上使用地板有什么原因吗？使用天花板会发生什么错误？

Answer 1

这完全取决于您如何更新 left 和 right 变量。

通常，我们使用 left = middle+1 和 right = middle-1，并带有停止条件 left = right。

在这种情况下，中间值的上限或下限并不重要。

但是，如果我们使用left = middle+1和right = middle，我们必须取中间值的底部，否则我们将陷入死循环.

考虑在数组 11, 22 中找到 11。

我们设置left = 0和right = 1，中间是0.5，如果取上限，就是1。由于 22 比查询大，我们需要切掉右半部分并将右边界向中间移动。当数组很大时这很好用，但因为只有两个元素。 right = middle 将再次将 right 设置为 1。我们有一个无限循环。

总结一下，

• 天花板和地板在 left = middle+1 和 right = middle-1 下都能正常工作
• 天花板适用于 left = middle 和 right = middle-1
• 地板在 left = middle+1 和 right = middle 下效果很好