在这里，汇集了搜索算法，包括线性查找、二分查找等。

代码实现

#include <iostream>
using namespace std;

int main()
{
    int nums[10];
    for (int i = 0; i < 10; i++)
    {
        nums[i] = i + 1;  // 初始化数组，1~10
    }

    int find;
    cin >> find;

    // 线性查找
    for (int i = 0; i < 10; i++)
    {
        if (nums[i] == find)
        {
            cout << i;  // 输出找到的索引
            return 0;
        }
    }

    cout << "Not found";  // 没找到
}

算法解析

这是最基本的查找算法，也是最简单的一种。

  1. 遍历数组
    • for (int i = 0; i < 10; i++)，依次检查 nums[i]
  2. 判断是否匹配
    • if (nums[i] == find)，如果找到目标值，就输出索引 i
  3. 提前返回
    • return 0; 避免多余的遍历，提高效率
  4. 未找到时输出 “Not found”
    • 遍历结束仍然没找到目标值，则打印 “Not found”

时间复杂度为 O(n)，适用于无序数组，或小规模数据

代码实现

#include<iostream>
using namespace std;

int main()
{
    int nums[10];
    for (int i = 0; i <= 9; i++)
    {
        nums[i] = i + 1;
    }

    int find = 0;                      // 要查找的元素
    int left = 0, right = 9;           // 元素下标
    int mid = 0;                       // 元素下标

    cin >> find;

    while (left <= right)
    {
        mid = (left + right) / 2;
        if (nums[mid] > find)
        {
            // 要找的元素在中点左边
            right = mid - 1;
            continue;
        } 
        if (nums[mid] < find)
        {
            //要找的元素在中点左边
            left = mid + 1;
            continue;
        }
        if (nums[mid] == find)
        {
            cout << mid;
            return 0;
        }
    }
    cout << "Not found";
}

算法解析

  1. 初始化
    • nums 数组被初始化为 {1, 2, 3, …, 10}，即 升序排列。
    • left = 0, right = 9，分别表示搜索范围的 左端 和 右端。
    • mid = (left + right) / 2，计算当前范围的 中间元素。
  2. 查找过程
    • 如果 nums[mid] > find，说明目标在 左半部分，所以更新 right = mid - 1。
    • 如果 nums[mid] < find，说明目标在 右半部分，所以更新 left = mid + 1。
    • 如果 nums[mid] == find，找到目标，输出索引并终止程序。
  3. 终止条件
    • 找到目标时，输出其索引并返回。
    • 若 left > right，表示搜索范围为空，目标元素不存在，输出 “Not found”。

时间复杂度

二分查找的时间复杂度是 O(log N)，原因是：

  1. 每次查找 都会把搜索范围缩小一半。
  2. 长度为 N 的数组，最多 log₂(N) 次 就能找到目标。

对于 N = 10：

最多 log₂(10) ≈ 3.3 ≈ 4 次迭代。

对于 n = 1,000,000：

最多 log₂(1000000) ≈ 20 次迭代，而线性查找 O(n) 最坏要 1,000,000 次。

仅适用于有序数组，为了使用二分查找而对数组进行排序是得不偿失的。

线性查找与二份查找对比

对比项线性查找二分查找
数据要求无序、有序都可以必须有序
时间复杂度（最坏情况）O(N)O(log N)
小规模数据快慢
大规模数据慢快
空间复杂度O(1)O(1)（迭代）/ O(log N)（递归）
适用场景小数据、无序数组大数据、有序数组
情况建议使用
无序数组线性查找
小数据集（N ≤ 100）线性查找
大数据集（N ≥ 1000）且有序二分查找
链表存储线性查找
频繁插入/删除数据线性查找（或哈希表）