此数组的二进制搜索需要多少次比较？

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，需要进行四个比较。这是为什么？

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.