如何找到递归二分查找的运行时间？

Question

对于下面的每个过程，设T (n)为运行时间。求T (n)的阶(即求f(n)使得T (n)∈(f(N)。

Procedure BinarySearch(table T [a . . . b], int k):
 if a > b then
  return -1
 end if
 middle ← ⌊(a + b)/2⌋
 if T [middle] = k then
  return middle
 end if
 if k < T [middle] then
  return BinarySearch(T [a . . .middle], k)
 else
  return BinarySearch(T [middle . . . b], k)
 end if

我知道如何找到简单函数的运行时，但由于这包括递归调用，所以我遇到了麻烦。

Answer 1

This link (页面底部)描述了一种非常清晰的方法来解决二进制搜索算法的递归关系。