问答题
编写一个递归算法实现在有序顺序表上的折半查找。算法的参数表中应增加两个形参left和right，分别指定算法在本层之下时的奁找区间均左、右端点。当查找成功时函数返回查找到的元素的存放位置；当查找不成功时函数返回-1。
递归算法的首部为int binarySearch1(seqList&L,DataType x,int left,int right)。主程序的调用方式为int loc=binarySearch1(L,x,0,L.n-1)。
【正确答案】
【答案解析】int binarySearch1 (seqList&L,DataType x,int left,int right) {
//在查找区间[left..right]采用折半查找算法查找与给定元素匹配的元素。
int mid=-1;
if (left＜=right){
mid=(left+right)/2;
if(x＞data[mid])mid=binarySearchl(L,x,mid+1,right);
//右缩区间
else if(x＜data[mid])mid=binarySearch(L,x,left,mid-1);
//左缩区间
}
return mid;
}
这个算法把规模为n的复杂问题经一次递归调用转化为一个规模减半的小子问题求解，再经过一次递归调用转化为规模再减半的更小子问题求解，如此继续，直到最终能够直接找到解为止。算法的时间复杂度为：T(n)=c+T(n/2)=c+(c+T(n/4))=2c+T(n/4)=2c+(c+T(n/8))=3c+T(n/8)=clog
2
n+T(1)。算法中用到一个递归工作栈，其规模与递归深度直接相关，也是O(log
2
n)。