查找算法¶

顺序查找¶

没有排序的数据：只能顺序查找。

例如：100万个数据，平均要找50万次！折半查找需要20次。

有的数据没有办法排序，就会使用顺序查找。

/// 顺序查找
/// @param a 指针 数组
/// @param n 数据的个数
/// @param x 要查找的数据
int SequentialSearch(int *a, const int n, const int x)
{
    int i;
    // 写一个循环，如果是要找的数，那么就return 返回数组下标
    for (i= 0; i < n; i++) {
        if (a[i] == x) {
            return i;
        }
    }
    //循环结束了 没找到
    return -1;
}

void test()
{
    int a[] = {2,4,6,8,0,1,3,5,7,9};
    int result;
    result = SequentialSearch(a, 10, 7);
    if (result < 0) {
        std::cout << "没找到" << std::endl;
    } else {
        std::cout << "在a[" << result << "]里找到" << std::endl;
    }
}

折半查找（二分查找）¶

查找速度快

前提条件：数据必须排好序。如果数据没有排好序就不能使用折半查找（二分查找）。

2²⁰ = 100万（就是1M）
2³⁰ = 10亿（就是1G）
例子：兰州拉面

迭代的折半查找

递归的折半查找

/// 折半查找
/// @param a 指针 数组
/// @param x 要查找的数据
/// @param n 数据的个数
int BinarySearch_I(int *a, const int x, const int n)//迭代
{
    int low, high, mid; // 三个下标
    low = 0, high = n - 1;
    //
    while (low <= high) { // 折半还没有结束
        mid = (low + high) / 2;
        if (a[mid] == x) { // 找到了
            return mid; // 返回下标
        } else if (a[mid] < x) {
            low = mid + 1; // 中间的数比要找的数小，则要找的数在大的那一半
        } else if (a[mid] > x) {
            high = mid - 1; // 要找的数比中间的数小，在小的那一半里面
        }
    }
    //循环结束了 没找到
    return -1;
}

//a是数组，x是要找的数
int BinarySearch_R(int *a, const int x, const int left, const int right)//递归
{
    if (left <= right) {
        //折半
        int middle = (left + right) / 2;
        if (x < a[middle]) {
            return BinarySearch_R(a, x, left, middle - 1);
        } else if (x > a[middle]) {
            return BinarySearch_R(a, x, middle + 1, right);
        } else {
            return middle;
        }
    }
    return -1;
}

调用：

void test()
{
    int m[] = {1,2,3,4,5,6,7,8,9};
    int result;
    int num = 7;
    if ((result = BinarySearch_R(m, num, 0, 8)) < 0) {
        std::cout << "递归算法：没找到" << std::endl;
    } else {
        std::cout << "递归算法：在m[" << result << "]找到" << num << std::endl;
    }
    if ((result = BinarySearch_I(m, num, 9)) < 0) {
        std::cout << "迭代算法：没找到" << std::endl;
    } else {
        std::cout << "迭代算法：在m[" << result << "]找到" << num << std::endl;
    }
}