查找算法¶

顺序查找¶

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

例如：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;
    }
}

查找两个数组中相同的元素¶

从数组B中筛选出那些其bsx属性值在数组A的asx属性值中出现的元素。

以下是一个Python代码示例，展示了如何实现这一过程：

# 定义数组A和B
A = [
    {"asx": " asd"}, 
    {"asx": "fdf }"}, 
    {"asx": "gfg "}, 
    {"asx": "das "}, 
    {"asx": " hth"}, 
]

B = [
    {"bsx": " asd"}, 
    {"bsx": "fdg }"}, 
    {"bsx": "gfhjg "}, 
    {"bsx": "jhte "}, 
    {"bsx": " hth"}, 
]

# 提取数组A中所有asx的值
a_values = {item["asx"] for item in A}

# 筛选数组B，只保留那些bsx的值出现在a_values中的元素
filtered_B = [item for item in B if item["bsx"] in a_values]

# 打印结果 [{'bsx': ' asd'}, {'bsx': ' hth'}]
print(filtered_B)

首先从数组A中提取所有asx的值，存储在一个集合a_values中。集合是一个非常适合这种类型的操作的数据结构，因为它可以快速检查一个元素是否存在于集合中。

接着，代码遍历数组B，检查每个元素的bsx值是否存在于a_values集合中。如果存在，这个元素就被包括在最终的filtered_B列表中。

这样，数组B就被过滤为只包含那些其bsx值在数组A的asx值中出现的元素。