分析执行Find(a,0,n-1,x)的时间复杂度

Question

int Find(ElemType a[ ],int s,int t,ElemType x)

{ int m=(s+t)/2;

 if (s<=t)

 {    if (a[m]==x)

          return m;

     else if (x<a[m])

          return Find(a,s,m-1,x);

     else

          return Find(a,m+1,t,x);

 }

 return -1;

}

Answer 1

是log(n)，可以改成T(n) = T(n/2) + a, T(1) = b，这样的形式求解然后目测得复杂度