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

  • Z时代
  • 2024-01-10
  • 分类：问答

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

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？还是不同的？

回答：

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

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

这导致了总共的2*log_2(n-1)比较，渐进地确实等于O(log(n))。

以上是 使用这种算法，在最坏的情况下二进制搜索会进行多少次比较？ 的全部内容， 来源链接： utcz.com/qa/404756.html

回到顶部