使用这种算法，在最坏的情况下二进制搜索会进行多少次比较？

使用这种算法，在最坏的情况下二进制搜索会进行多少次比较？

在这种情况下，最坏的情况是，如果元素K在A中不存在并且小于A中的所有元素。那么在每个步骤中我们有两个比较：

K > A[m]

和

K < A[m]

。

因为在每一步中，数组都被切成两部分，每个部分的大小为

(n-1)/2

，所以我们有最多的

log_2(n-1)

步骤。

这导致了总共的

2*log_2(n-1)

比较，渐进地确实等于

O(log(n))

。