试题四（共15分）

阅读以下说明、C函数和问题，回答问题1和问题2将解答填入答题纸的对应栏内。

【说明】

当数组中的元素已经排列有序时，可以采用折半查找（二分查找）法查找一个元素。下面的函数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<r[mid])

（2）;

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<r[mid])

return biSearch_rec(（5）,key);

else

return biSearch_rec(（6）,key);

 }/*if*/

return -1;

}/*biSearch_rec*/

问题一：关于二分查找函数的填空部分，关键在于理解二分查找的原理和流程。首先，需要保证数组范围有效，即low和high定义了数组的边界。在每一次循环中，通过计算中间值mid来缩小搜索范围。如果key等于r[mid]，则找到了目标元素；如果key小于r[mid]，则在左半边继续查找；如果key大于r[mid]，则在右半边继续查找。这个过程在递归和非递归版本的函数中是一样的。因此，（1）、（2）、（3）、（4）的填空答案分别为low <= high 或 low < high、biSearch(r, low, mid-1, key)、biSearch(r, mid+1, high, key)、low <= high。（5）、（6）的填空答案为递归查找左半边和右半边的参数，即r[], low, mid-1和r[], mid+1, high。
问题二：关于二分查找的比较次数，由于每次比较后搜索范围都会减半，所以最多比较次数为log2(n+1)。这是因为二分查找的核心思想是将数据不断二分，直到找到目标元素或确定元素不存在。因此，答案选A。