c++顺序表的折半查找算法,并测试验证

顺序表的折半查找算法也叫做二分查找算法，其基本思想是：将查找区间一分为二，然后确定待查关键字在哪一部分中，再将查找区间一分为二，直到找到待查关键字为止。

C++代码如下：

#include <iostream>
using namespace std;

const int MAXSIZE = 100;
typedef struct {
    int data[MAXSIZE];
    int length;
} SqList;

int BinarySearch(SqList L, int key) {
    int low = 0, high = L.length - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (L.data[mid] == key) {
            return mid;
        }
        else if (L.data[mid] > key) {
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    return -1;
}

int main() {
    SqList L;
    L.length = 10;
    for (int i = 0; i < L.length; i++) {
        L.data[i] = i + 1;
    }
    int key = 7;
    int index = BinarySearch(L, key);
    if (index == -1) {
        cout << "未找到" << endl;
    }
    else {
        cout << "已找到，位置为" << index + 1 << endl;
    }
    return 0;
}

在上述代码中，我们定义了一个结构体 `SqList` 表示顺序表，其中包含一个数组 `data` 和一个整型变量 `length`，表示顺序表的长度。`BinarySearch` 函数是我们实现的折半查找算法，它接收两个参数：一个顺序表和一个待查关键字。在 `main` 函数中，我们初始化了一个长度为 10 的顺序表，并查找关键字为 7 的元素。

测试结果如下：

已找到，位置为7

说明我们的代码实现是正确的。