多少次比较将二进制搜索在使用这种算法的最坏情况做？(How many comparisons wil

您好以下是我的二进制搜索实现的伪代码：

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 -元素阵列（ n > 0 ），比较元件是在索引m = floor((n-1)/2) 因此，有三种可能性

A[m] < K则一个比较之后，搜索在继续n-1-m = ceiling((n-1)/2) -元素数组。
A[m] > K ，然后两个比较之后，搜索在继续m -元素数组。
A[m] == K ，然后我们两个比较后进行。

因此，如果我们表示的最大（最坏情况）的比较的数目用于在搜索n通过-元素阵列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 ，其中>>>是无符号向右移位运算符。阅读更多关于这个问题在这里。

文章来源: How many comparisons will binary search make in the worst case using this algorithm?