多少次比较会使用该算法的最坏情况下的二进制搜索做什么呢？ [英] How many comparisons will binary search make in the worst case using this algorithm?

问题描述

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

Hi there below is the pseudo code for my binary search implementation:

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的有序数组？

I was just wondering how to calculate the number of comparisons this implementation would make in the worst case for a sorted array of size n?

请问比较的数量= LG n + 1个？或不同的东西？

Would the number of comparisons = lg n + 1? or something different?

推荐答案

在最坏的情况下在这种情况下，如果元素K不present A和比A.然后我们有两个要素都较小在每一步的比较： K＆GT; A [M] 和 K＆LT; A [M] 。

The worst-case in this case is, if the element K is not present in A and smaller than all elements in A. Then we have two comparisons in each step: K > A[m] and K < A[m].

有关在每个步骤中，阵列被切成两部分，每部分的大小（N-1）/ 2 ，我们有一个最大的 log_2（N-1）步骤。

For in each step the array is being cut into two parts, each of the size (n-1)/2, we have a maximum of log_2(n-1) steps.

这导致了总 2 * log_2（N-1）比较，这渐近实际上等于 O（日志（N）） 。

This leads to a total of 2*log_2(n-1) comparisons, which asymptotically indeed equals to O(log(n)).

这篇关于多少次比较会使用该算法的最坏情况下的二进制搜索做什么呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！