您好，下面是我的二进制搜索实现的伪代码:
Input: (A[0...n-1], K)
begin
l ← 0; r ← n-1
while l ≤ r do
m ← floor((l+r)/2)
if K > A[m] then l ← m+1
else if K < A[m] then r ← m-1 else return m
end if
end while
return -1 // key not found
end
我只是想知道如何计算此实现在最坏情况下对大小为 n 的排序数组进行比较的次数？
请问比较次数=lgn+1？还是不同的东西？
最佳答案
在这种情况下最坏的情况是，如果元素 K 不存在于 A 中并且小于 A 中的所有元素。那么我们在每个步骤中进行两次比较:K > A[m]和 K < A[m] .
因为在每一步中，数组都被分成两部分，每个部分的大小为 (n-1)/2 ，我们最多有 log_2(n-1)步骤。
这导致总共 2*log_2(n-1)比较，渐近地确实等于 O(log(n)) .
关于arrays - 使用此算法在最坏情况下二分查找将进行多少次比较？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10571170/