试题四
阅读以下说明、 C 函数和问题， 回答问题，将解答填入答题纸的对应栏内。
【说明】
当数组中的元素已经排列有序时， 可以采用折半查找（二分查找） 法查找一个元素。 下面的函数 biSearch(int r[]， int low， int high， int key)用非递归方式在数组 r 中进行二分查找， 函数 biSearch_rec(int r[]， int low， int high， int key)采用递归方式在数组 r 中进行二分查找， 函数的返回值都为所找到元素的下标； 若找不到， 则返回-1。
【C 函数 1】
int biSearch(int r[]， int low， int high， int key)
//r[low..high] 中的元素按非递减顺序排列
//用二分查找法在数组 r 中查找与 key 相同的元素
//若找到则返回该元素在数组 r 的下标， 否则返回-1
{
int mid;
while(（1） ) {
mid = (low+high)/2 ;
if (key ==r[mid])
return mid;
else if (key
else
（3） ;
}/*while*/
return -1;
}/*biSearch*/
【C 函数 2】
int biSearch_rec(int r[]， int low， int high， int key)
//r[low..high]中的元素按非递减顺序排列
//用二分查找法在数组 r 中查找与 key 相同的元素
//若找到则返回该元素在数组 r 的下标， 否则返回-1
{
int mid;
if(（4） ) {
mid = (low+high)/2 ;
if (key ==r[mid])
return mid;
else if (key
else
return biSearch_rec(（6） ,key);
}/*if*/
return -1;
}/*biSearch_rec*/
请填充 C 函数 1 和 C 函数 2 中的空缺， 将解答填入答题纸的对应栏内。
（1）low<=high
（2） high=mid-1
（3） low=mid+1
（4） low<=high
（5） low,mid-1
（6） mid+1,high
本题考察折半查找。 二分查找又称折半查找， 优点是比较次数少， 查找速度快， 平均性能好，占用系统内存较少； 其缺点是要求待查表为有序表， 且插入删除困难。 因此， 折半查找方法适用于不经常变动而查找频繁的有序列表。 首先， 假设表中元素是按升序排列， 将表中间位置记录的关键字与查找关键字比较， 如果两者相等， 则查找成功； 否则利用中间位置记录将表分成前、 后两个子表， 如果中间位置记录的关键字大于查找关键字， 则进一步查找前一子表， 否则进一步查找后一子表。 重复以上过程， 直到找到满足条件的记录， 使查找成功， 或直到子表不存在为止， 此时查找不成功。
二分查找的基本思想是将 n 个元素分成大致相等的两部分， 取 a[n/2]与 x 做比较， 如果x=a[n/2],则找到 x,算法中止； 如果 x
若有序数组中有 n 个元素， 采用二分查找法查找一个元素时， 最多与（ ） 个数组元素进行比较， 即可确定查找结果。
（7） 备选答案：
A.[log2(n+1)] B.[n/2] C.n-1 D.n
（7）A