小编Har*_*ron的帖子

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

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

嗨,我试图通过伸缩解决以下复发关系,但我被困在最后一步.

T(N) = T(N/2) + N              T(1)=0
T(N/2) = T(N/4) + N/2
T(N/4) = T(N/8) + N/4
...
T(2) = T(1) + 2

T(N)= T(1) + N + N/2 + N/4

我认为答案是nlogn,但我不知道如何将上述解释为nlogn.我可以看到我正在做logn步骤但是n来自哪里？