算法设计题 :已知n元顺序表a0, a1, … , an-1按关键字递增有序存储。给定关键字值

设计算法，在表中折半查找该关键字，若找到则返回其下标，否则返回-1。

折半查找（Binary Search）又称二分查找，是在一个有序数组中查找某一特定元素的搜索算法。它采用二分策略，将待查元素与中间元素作比较，如果待查元素大于中间元素，则在数组大于中间位置的一半继续查找，否则在小于中间位置的一半继续查找，直到查找到该元素或发现该元素不存在为止。

以下是一种简单的折半查找算法：

1. 初始化左边界left为0，右边界right为n-1；
2. 重复下列步骤直到找到关键字或确定关键字不存在：
1)计算中间位置mid=(left+right)/2；
2)比较a[mid]与给定关键字的值：
·若a[mid]>key，则说明关键字在a[left..mid-1]之间，令right=mid-1；
·若a[mid]<key，则说明关键字在a[mid+1..right]之间，令left=mid+1；
·若a[mid]=key，则说明找到关键字，返回mid。

实现以上算法的代码为：

int binarySearch(int a[], int n, int key){
int left = 0, right = n - 1;
while(left <= right){
int mid = (left + right) / 2;
if(a[mid] > key)
right = mid - 1;
else if(a[mid] < key)
left = mid + 1;
else
return mid;
}
return -1;
}

该算法的时间复杂度为O(log n)，是一种效率较高的查找算法。