用递归算法确定递归关系

Question

我得到了以下递归算法，并被要求找出它的递归关系。

int search(int A[], int key, int min, int max)
{
    if (max < min)      // base case
       return KEY_NOT_FOUND;
    else
    {
       int mid = midpoint(min, max);
       if (A[mid] > key)    
          return search(A, key, min, mid-1);
       else if (A[mid] < key)
          return search(A, key, mid+1, max);
       else
          return mid;       // key found
    }
}

解决方案是T(n) = T(n/2) + 1，但我不确定为什么是T(n/2) ?为什么是+ 1 ?+ 1是因为递归需要常数时间吗?还是别的什么?有人能理解这个解决方案吗?

Answer 1

您的代码是二进制搜索的实现。在二元查找中，在每次递归调用时，将排序数组分成两半，如果元素小于中间元素，则搜索数组的左侧元素;如果元素大于中间元素，则搜索数组的右侧元素;如果查找的是中间元素，则停止。

现在，如果n表示排序数组中的元素数量，无论何时将其分解为两个大小几乎相同的数组，问题的大小都会减小到n/2，并且由于在n/2数组中，无论如何只调用一次搜索函数，您可以轻松地说:

T(n) = T(n/2)+O(1)

0(1)的增加是因为如果你运行检查你所处的条件