首页 文章

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

提问于
浏览 次
16

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

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？还是别的什么？

arrays algorithm complexity-theory binary-search

3 回答

  • 10

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

    因为在每个步骤中，数组被切割成两个部分，每个部分的大小为 (n-1)/2 ，我们最多有 log_2(n-1) 个步骤 .

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

    回复于
  • 5

    对hielsnoppe's answer的一个非常小的修正：

    在 n -element数组（ n > 0 ）中，要比较的元素位于索引 m = floor((n-1)/2) . 所以有三种可能性

    • A[m] < K ，然后在一次比较之后，搜索在 n-1-m = ceiling((n-1)/2) -element数组中继续 .

    • A[m] > K ，然后在两次比较后，搜索在 m -element数组中继续 .

    • A[m] == K ，然后我们在两次比较后完成了 .

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

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

    这是一个确切的上限 .

    回复于
  • 15

    根据binary search上的维基百科页面，该算法的最坏情况性能是 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 ，其中 >>> 是无符号右移运算符 . 在here中阅读有关该问题的更多信息 .

    回复于

相关问题