C++实现查找算法和折半查找算法

1. 查找算法（线性查找）

线性查找又叫顺序查找，是一种基础的查找算法。顾名思义，就是按照数据的顺序依次进行查找，直到找到目标数据或者遍历完整个数据集为止。

C++代码实现如下：

#include <iostream>
using namespace std;

int search(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1; // 未找到目标数据
}

int main() {
    int arr[] = { 2, 5, 3, 7, 9, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 7;
    int index = search(arr, n, x);
    if (index == -1) {
        cout << "未找到目标数据！" << endl;
    } else {
        cout << "目标数据在数组中的下标为：" << index << endl;
    }
    return 0;
}

2. 折半查找算法

折半查找又叫二分查找，是一种高效的查找算法。前提条件是数据已经排好序。折半查找的思路是将数据集分成两部分，判断目标数据在哪一部分，然后在该部分中继续进行查找，直到找到目标数据或者确定目标数据不存在为止。

C++代码实现如下：

#include <iostream>
using namespace std;

int binarySearch(int arr[], int low, int high, int x) {
    if (low > high) {
        return -1; // 未找到目标数据
    }
    int mid = (low + high) / 2;
    if (arr[mid] == x) {
        return mid;
    } else if (arr[mid] > x) {
        return binarySearch(arr, low, mid - 1, x);
    } else {
        return binarySearch(arr, mid + 1, high, x);
    }
}

int main() {
    int arr[] = { 1, 2, 3, 5, 7, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 7;
    int index = binarySearch(arr, 0, n - 1, x);
    if (index == -1) {
        cout << "未找到目标数据！" << endl;
    } else {
        cout << "目标数据在数组中的下标为：" << index << endl;
    }
    return 0;
}