实现基于有序顺序表的折半查找算法

折半查找算法，也称为二分查找算法，是一种常用的查找算法。它要求查找表是有序的，根据查找表中间位置的关键字与待查关键字的比较结果，将查找区间缩小为表的一半，直到找到待查元素或查找区间为空为止。

基于有序顺序表的折半查找算法的实现步骤如下：

1. 定义一个有序顺序表，包含元素的关键字按照从小到大的顺序排列。

2. 定义待查元素的关键字 key。

3. 定义查找区间的左边界 left 和右边界 right，初始时 left=0，right=n-1，其中 n 是顺序表的长度。

4. 当 left<=right 时，执行以下步骤：

(1) 计算中间位置 mid = (left + right) / 2。

(2) 如果中间位置的关键字等于待查关键字 key，则返回 mid。

(3) 如果中间位置的关键字大于待查关键字 key，则在左半区间继续查找，将右边界 right 更新为 mid-1。

(4) 如果中间位置的关键字小于待查关键字 key，则在右半区间继续查找，将左边界 left 更新为 mid+1。

5. 如果查找区间为空，即 left>right，则返回查找失败。

以下是基于有序顺序表的折半查找算法的 C++ 实现：

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) return mid;
        else if (a[mid] > key) right = mid - 1;
        else left = mid + 1;
    }
    return -1;  // 查找失败
}