algorithm - 算法的时间复杂度

Question

我编写了一个算法，用于在无限整数的排序数组中查找键。

 findKey(int k, int start, int end)
     int mid = (start + end)/2

     if (k < array[mid])
         findKey(k, start, mid)
     else if (k > array[mid])
         findKey(k, mid+1, end)
     else 
         return mid

我想知道这个算法的时间复杂度。是o（logn）吗？我真的很困惑，谁能解释一下？也让我知道这里是否有任何缺陷。提前致谢。

Answer 1

让我们有存储值的数组

假设我们要找到key=20，我们调用findkey(20,1,8)，参数k=20，start=1，end=8

一系列函数调用

Recurrence relation :

T(n)  = T(n/2)+c
 expanding…
          =T(n/2^2)+c+c
          =T(n/2^3)+c+c+c

Kth time expanding…

          = c+c+c+c+c . .. .. . .. . . .  .T(n/2^k)

Let at kth time array size become 1,
we assume it as a base condition for recurrence.
Thus , 
   n/2^k = 1
      n  = 2^k
Taking log both sides ..
    log n = k

 time complexity of recurrence..

   T(n) = c* log n 
        = O(log n) 

Answer 2

你所做的是二分搜索算法，或者接近它的东西。该算法为 O(log n)。