algorithm - 这个数组的二分查找需要多少次比较？

Question

我们有以下数组： [4, 13, 25, 33, 38, 41, 55, 71, 73, 84, 86, 92, 97] 对我来说似乎只需要 3 次比较即可找到 25，因为：首先我们选择中间元素 55。现在我们执行两次比较：55 = 25？55 > 25？这些都不成立，所以我们转到数组的左侧。我们得到子数组：[4, 13, 25, 33, 38, 41] 我们再次除以得到 25 = 25？是的.. 所以我们需要 3 次比较才能得到我们的匹配。我的书说要找到 25 需要进行四次比较。这是为什么呢？

标签： algorithmbinary-search

Answer 1

由于左侧数组的大小是偶数，因此每个算法都可以选择中间数字之一。因此，比较可能如下所示，进行 4 次比较：

[4, 13, 25, 33, 38, 41, 55, 71, 73, 84, 86, 92, 97]
25 < 55 =>‌ [4, 13, 25, 33, 38, 41]
25 < 33 => [4, 13, 25]
25 > 13 => [25]
25 == 25 => Found.