20

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

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？或不同的东西？

4

3 回答 3

20

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

因为在每一步中，数组都被分成两部分，每部分的大小(n-1)/2，我们有最大的log_2(n-1)步骤。

这导致总2*log_2(n-1)比较，渐近确实等于O(log(n))。

于 2012-05-13T11:23:19.193 回答
12

对hielsnoppe 的回答的一个非常小的修正：

在n-element 数组 ( n > 0) 中，要比较的元素位于 index 处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)))).

这是一个确切的上限。

于 2012-05-13T13:25:37.600 回答
6

根据 wikipedia page on binary search，该算法的最坏情况性能是O(lg n)，它测量所需比较的渐近次数。正如@hielsnoppe 的回答所指出的那样，实际最坏情况的比较次数是。2*lg(n-1)

问题中的伪代码表示二进制搜索的典型实现，因此预期的性能复杂性适用于 size 的数组（或向量）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，>>>无符号右移运算符在哪里。在此处阅读有关该问题的更多信息。
于 2012-05-13T11:11:21.303 回答