想分析递归线性搜索的复杂性(使用分治技术)。是 log(n) 还是 n ?如果不是 log(n) 那么实际复杂性是多少以及如何?
int linear_search(int *a,int l,int h,int key){
if(h == l){
if(key == a[l])
return l;
else
return -1;
}
int mid =(l+h)/2;
int i = linear_search(a,l,mid,key);
if(i == -1)
i = linear_search(a,mid+1,h,key);
return i;
}