C++搜索算法详解（从零开始掌握线性搜索与二分查找）

1. 线性搜索（Linear Search）

线性搜索是最简单、最直观的搜索方式。它从数组的第一个元素开始，逐个检查每个元素，直到找到目标值或遍历完整个数组。

优点：实现简单，适用于无序数组。
缺点：效率低，时间复杂度为 O(n)。

C++ 线性搜索代码示例：

#include <iostream>#include <vector>// 线性搜索函数int linearSearch(const std::vector<int>& arr, int target) {    for (int i = 0; i < arr.size(); ++i) {        if (arr[i] == target) {            return i; // 返回目标元素的索引        }    }    return -1; // 未找到，返回-1}int main() {    std::vector<int> numbers = {10, 25, 3, 47, 15, 8};    int target = 47;    int result = linearSearch(numbers, target);    if (result != -1) {        std::cout << "找到目标值 " << target                   << "，位置在索引: " << result << std::endl;    } else {        std::cout << "未找到目标值 " << target << std::endl;    }    return 0;}

2. 二分查找（Binary Search）

二分查找是一种高效的搜索算法，但前提是数组必须是有序的。它的基本思想是：每次将搜索范围缩小一半，从而快速逼近目标值。

优点：效率高，时间复杂度仅为 O(log n)。
缺点：要求数据已排序，不适合频繁变动的数据集。

C++ 二分查找代码示例（递归版）：

#include <iostream>#include <vector>// 递归实现的二分查找int binarySearch(const std::vector<int>& arr, int left, int right, int target) {    if (left > right) {        return -1; // 未找到    }    int mid = left + (right - left) / 2;    if (arr[mid] == target) {        return mid;    } else if (arr[mid] > target) {        return binarySearch(arr, left, mid - 1, target);    } else {        return binarySearch(arr, mid + 1, right, target);    }}int main() {    std::vector<int> sortedNumbers = {3, 8, 10, 15, 25, 47}; // 必须是有序的！    int target = 15;    int result = binarySearch(sortedNumbers, 0, sortedNumbers.size() - 1, target);    if (result != -1) {        std::cout << "找到目标值 " << target                   << "，位置在索引: " << result << std::endl;    } else {        std::cout << "未找到目标值 " << target << std::endl;    }    return 0;}

如何选择合适的搜索算法？

• 如果你的数据是无序的，或者数据量很小（比如少于100个元素），使用线性搜索即可。
• 如果你的数据是有序的，并且需要频繁查找，那么C++二分查找是更优的选择。
• 对于超大规模数据，还可以考虑哈希表（unordered_map）等更高级的数据结构。

总结

通过本篇算法入门教程，你已经掌握了两种最基本的 C++ 搜索方法：线性搜索和二分查找。记住，C++搜索算法不仅是面试常考内容，更是实际开发中提升程序效率的关键工具。

动手实践是掌握算法的最佳方式！尝试修改上面的代码，用不同的数据测试它们的运行结果吧。