顺序查找和折半查找c++

顺序查找（也称线性查找）是一种简单的查找算法，它逐个比较查找表中的元素，直到找到相应的元素或查找完整个表为止。C++ 中实现顺序查找可以使用 for 循环或 while 循环实现，代码示例如下：

int seq_search(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i;   // 找到了，返回索引
        }
    }
    return -1;  // 没有找到，返回 -1
}

折半查找（也称二分查找）是一种高效的查找算法，它要求待查找的表是有序的。查找过程中，每次将待查找区间缩小为原来的一半，直到找到元素或区间为空为止。C++ 中实现折半查找可以使用递归或循环实现，代码示例如下：

// 递归实现折半查找
int binary_search(int arr[], int left, int right, int key) {
    if (left > right) {
        return -1;  // 没有找到，返回 -1
    }
    int mid = (left + right) / 2;
    if (arr[mid] == key) {
        return mid; // 找到了，返回索引
    } else if (arr[mid] > key) {
        return binary_search(arr, left, mid - 1, key); // 在左半边查找
    } else {
        return binary_search(arr, mid + 1, right, key); // 在右半边查找
    }
}

// 循环实现折半查找
int binary_search(int arr[], int n, int key) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == key) {
            return mid; // 找到了，返回索引
        } else if (arr[mid] > key) {
            right = mid - 1; // 在左半边查找
        } else {
            left = mid + 1; // 在右半边查找
        }
    }
    return -1; // 没有找到，返回 -1
}