【C++】数据结构与算法：常用查找算法

😏★,°:.☆(￣▽￣)/$:.°★ 😏
这篇文章主要介绍常用查找算法。
学其所用，用其所学。——梁启超
欢迎来到我的博客，一起学习，共同进步。
喜欢的朋友可以关注一下，下次更新不迷路🥞

😏1. 算法介绍

查找算法的作用是在给定的数据集合中搜索目标元素或确定目标元素是否存在。它可以帮助我们快速地找到所需的数据，提供有效的数据访问和处理方式。

常用的查找算法有以下几种：

1. 线性查找：也称为顺序查找，是最简单直接的查找算法。它从数据结构的起始位置开始，逐个比较元素，直到找到目标元素或遍历完整个数据结构。时间复杂度为O(n)，其中n是数据结构中元素的个数。

2. 二分查找：适用于已排序的数据结构（如有序数组）。它将目标元素与中间元素进行比较，根据比较结果确定目标元素在左半部分还是右半部分，并继续在该部分进行查找。通过每次排除一半的元素，二分查找能够快速定位目标元素。时间复杂度为O(log n)。

3. 哈希表查找：利用哈希表数据结构实现的查找算法。哈希表根据关键字的哈希值存储元素，并提供快速的查找操作。通过将关键字映射到哈希表的索引位置，可以在常数时间内（平均情况下）找到目标元素。哈希表查找的平均时间复杂度是O(1)，但在最坏情况下可能达到O(n)。

4. 二叉搜索树查找：利用二叉搜索树数据结构实现的查找算法。二叉搜索树是一颗有序二叉树，对于树中的每个节点，左子树中的所有节点的值小于当前节点的值，右子树中的所有节点的值大于当前节点的值。通过比较目标值与当前节点的值，可以决定继续在左子树还是右子树中进行查找。二叉搜索树查找的平均时间复杂度为O(log n)，但在最坏情况下可能达到O(n)。

5. 平衡二叉搜索树查找：为了解决二叉搜索树在某些情况下退化成链表的问题，引入了平衡二叉搜索树（如AVL树、红黑树）。这些树通过自平衡机制保持树的平衡性，从而保证查找操作的平均时间复杂度为O(log n)。

6. 插值查找：是二分查找的变体，用于在有序数组中进行查找。它不像二分查找每次都将查找范围一分为二，而是根据目标值与数组元素的分布情况，在靠近目标值的位置更有可能找到目标元素。最好情况下的时间复杂度为O(1)，最坏情况下为O(n)，平均情况下为O(log log n)。

😊2. C++实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>// 线性查找
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;  // 没有找到目标元素
}// 二分查找（针对已排序数组）
int binarySearch(const std::vector<int>& arr, int target) {int left = 0;int right = arr.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;  // 没有找到目标元素
}// 哈希表查找
int hashTableSearch(const std::unordered_map<int, int>& table, int target) {auto it = table.find(target);if (it != table.end()) {return it->second;}return -1;  // 没有找到目标元素
}int main() {std::vector<int> arr = {10, 25, 4, 15, 8, 36};// 线性查找int target1 = 15;int index1 = linearSearch(arr, target1);if (index1 != -1) {std::cout << "线性查找：" << target1 << " 的索引为 " << index1 << std::endl;} else {std::cout << "线性查找：没有找到 " << target1 << std::endl;}// 二分查找前需要将数组排序std::sort(arr.begin(), arr.end());// 二分查找int target2 = 25;int index2 = binarySearch(arr, target2);if (index2 != -1) {std::cout << "二分查找：" << target2 << " 的索引为 " << index2 << std::endl;} else {std::cout << "二分查找：没有找到 " << target2 << std::endl;}// 哈希表查找std::unordered_map<int, int> table;for (int i = 0; i < arr.size(); i++) {table[arr[i]] = i;}int target3 = 8;int index3 = hashTableSearch(table, target3);if (index3 != -1) {std::cout << "哈希表查找：" << target3 << " 的索引为 " << index3 << std::endl;} else {std::cout << "哈希表查找：没有找到 " << target3 << std::endl;}return 0;
}

编译运行：

g++ -o main main.cpp && ./main
线性查找：15 的索引为 3
二分查找：25 的索引为 4
哈希表查找：8 的索引为 1

以上。