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

Question

您好,下面是我的二进制搜索实现的伪代码:

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的排序数组进行的比较次数？

比较次数是否= lg n + 1？还是别的什么？

Answer 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)).

Answer 2

对hielsnoppe答案的一个非常小的修正:

在n-element array(n > 0)中,要比较的元素是索引m = floor((n-1)/2).所以有三种可能性

1. A[m] < K然后在一次比较之后,搜索在n-1-m = ceiling((n-1)/2)-element数组中继续.
2. A[m] > K然后在两次比较之后,搜索在m-element数组中继续.
3. A[m] == K,然后我们在两次比较后完成.

因此,如果我们用n-element数组表示搜索的最大(最坏情况)比较次数C(n),我们有

C(0) = 0
C(n) = max { 1 + C(ceiling((n-1)/2), 2 + C(floor((n-1)/2) }, n > 0

对于奇数n = 2k+1,地板和天花板是相同的,所以最大值显然是后者,

C(2k+1) = 2 + C(k)

甚至n = 2k,我们发现

C(2k) = max { 1 + C(k), 2 + C(k-1) }.

对于n = 2,解析为C(2) = 1 + C(1) = 1 + 2 = 3,对所有更大n,最大的是2 + C(k-1),由于n >= 1我们有C(n) <= C(n+1) <= C(n) + 1.

n我们发现,评估前几个的递归

C(0) = 0
C(1) = 2
C(2) = 3
C(3) = C(4) = 4
C(5) = C(6) = 5
C(7) = C(8) = C(9) = C(10) = 6
C(11) = ... = C(14) = 7
C(15) = ... = C(22) = 8
C(23) = ... = C(30) = 9

所以通过归纳我们证明了

C(n) = 2k, if 2^k <= n+1 < 2k + 2^(k-1), and
C(n) = 2k+1, if 2^k + 2^(k-1) <= n+1 < 2^(k+1)

要么

C(n) = 2*log2(n+1) + floor(2*(n+1)/(3*2^floor(log2(n+1)))).

这是一个确切的上限.

Answer 3

根据关于二进制搜索的维基百科页面,该算法的最坏情况性能是O(lg n),它测量所需的渐近数量的比较.在实际比较的最坏情况数目将是2*lg(n-1),正如已经指出在@ hielsnoppe的答案.

问题中的伪代码表示二进制搜索的典型实现,因此预期的性能复杂性适用于大小的数组(或向量)n:

• 最佳案例表现: O(1)
• 平均案例表现: O(lg n)
• 最坏情况表现: O(lg n)

仔细观察,问题中的伪代码存在两个问题:

• 这一行:if K > A[m] then return l ? m+1应该读if K > A[m] then l ? m+1.你还不能回来
• 该行:m ? floor((l+r)/2)当使用固定大小的整数时,如果数字足够大,可能会导致溢出.正确的语法取决于您正在使用的实际编程语言,但是这样可以解决问题:m ? (l + r) >>> 1,>>>无符号右移运算符在哪里.在这里阅读有关此问题的更多信息.