查找算法¶
📖 章节简介¶
本章将介绍C++的常用查找算法，包括二分查找、哈希表和平衡树。
上图对比了线性查找、二分查找和哈希查找在前提条件与复杂度上的差异，便于快速选型。
🔍 二分查找¶
1. 迭代实现¶
C++
// 二分查找（迭代）
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(const vector<int>& arr, int target) {
if (arr.empty()) return -1; // 防止 size()-1 无符号下溢
int left = 0;
int right = static_cast<int>(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 main() {
vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int target = 13;
cout << "数组：";
for (int num : arr) {
cout << num << " ";
}
cout << "\n查找目标: " << target << endl;
int index = binarySearch(arr, target);
if (index != -1) {
cout << "找到目标，索引: " << index << endl;
} else {
cout << "未找到目标" << endl;
}
return 0;
}
2. 递归实现¶
C++
// 二分查找（递归）
#include <iostream>
#include <vector>
using namespace std;
int binarySearchRecursive(const vector<int>& arr, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binarySearchRecursive(arr, target, mid + 1, right);
} else {
return binarySearchRecursive(arr, target, left, mid - 1);
}
}
int main() {
vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int target = 13;
cout << "数组：";
for (int num : arr) {
cout << num << " ";
}
cout << "\n查找目标: " << target << endl;
// 注意：arr.size() 返回 size_t（无符号），空数组时 size()-1 会下溢
int index = arr.empty() ? -1
: binarySearchRecursive(arr, target, 0, static_cast<int>(arr.size()) - 1);
if (index != -1) {
cout << "找到目标，索引: " << index << endl;
} else {
cout << "未找到目标" << endl;
}
return 0;
}
📊 哈希表¶
1. 链地址法（拉链法）¶
C++
// 链地址法哈希表
#include <iostream>
#include <vector>
#include <list>
using namespace std;
class HashTable {
private:
vector<list<pair<int, string>>> table;
int size;
int hashFunction(int key) {
return key % size;
}
public:
HashTable(int tableSize) {
size = tableSize;
table.resize(tableSize);
}
void insert(int key, const string& value) {
int index = hashFunction(key);
table[index].push_back({key, value});
}
string search(int key) {
int index = hashFunction(key);
for (const auto& pair : table[index]) {
if (pair.first == key) {
return pair.second;
}
}
return "";
}
bool remove(int key) {
int index = hashFunction(key);
for (auto it = table[index].begin(); it != table[index].end(); ++it) {
if (it->first == key) {
table[index].erase(it);
return true;
}
}
return false;
}
void display() {
for (int i = 0; i < size; i++) {
cout << "Bucket " << i << ": ";
for (const auto& pair : table[i]) {
cout << "[" << pair.first << ":" << pair.second << "] ";
}
cout << endl;
}
}
};
int main() {
HashTable ht(10);
// 插入键值对
ht.insert(1, "张三");
ht.insert(2, "李四");
ht.insert(12, "王五");
ht.insert(3, "赵六");
ht.insert(13, "钱七");
// 显示哈希表
cout << "哈希表内容：" << endl;
ht.display();
// 查找
cout << "\n查找key=3: " << ht.search(3) << endl;
cout << "查找key=12: " << ht.search(12) << endl;
// 删除
cout << "\n删除key=2" << endl;
bool removed = ht.remove(2);
cout << "删除" << (removed ? "成功" : "失败") << endl;
// 再次显示
cout << "\n删除后的哈希表：" << endl;
ht.display();
return 0;
}
🌳 平衡树¶
1. AVL树¶
C++
// AVL树（简化版）
#include <iostream>
#include <algorithm>
using namespace std;
struct AVLNode {
int data;
AVLNode* left;
AVLNode* right;
int height;
AVLNode(int val) : data(val), left(nullptr), right(nullptr), height(1) {}
};
class AVLTree {
private:
AVLNode* root;
int height(AVLNode* node) {
if (node == nullptr) {
return 0;
}
return node->height;
}
int balanceFactor(AVLNode* node) {
if (node == nullptr) {
return 0;
}
return height(node->left) - height(node->right);
}
void updateHeight(AVLNode* node) {
node->height = 1 + max(height(node->left), height(node->right));
}
AVLNode* rotateRight(AVLNode* y) {
AVLNode* x = y->left;
y->left = x->right;
x->right = y;
updateHeight(y);
updateHeight(x);
return x;
}
AVLNode* rotateLeft(AVLNode* x) {
AVLNode* y = x->right;
x->right = y->left;
y->left = x;
updateHeight(x);
updateHeight(y);
return y;
}
AVLNode* balance(AVLNode* node) {
if (node == nullptr) {
return node;
}
int bf = balanceFactor(node);
// 左左情况
if (bf > 1 && balanceFactor(node->left) >= 0) {
return rotateRight(node);
}
// 右右情况
if (bf < -1 && balanceFactor(node->right) <= 0) {
return rotateLeft(node);
}
// 左右情况
if (bf > 1 && balanceFactor(node->left) < 0) {
node->left = rotateLeft(node->left);
return rotateRight(node);
}
// 右左情况
if (bf < -1 && balanceFactor(node->right) > 0) {
node->right = rotateRight(node->right);
return rotateLeft(node);
}
return node;
}
AVLNode* insert(AVLNode* node, int key) {
if (node == nullptr) {
return new AVLNode(key);
}
if (key < node->data) {
node->left = insert(node->left, key);
} else if (key > node->data) {
node->right = insert(node->right, key);
} else {
return node; // 重复键
}
updateHeight(node);
return balance(node);
}
void inorder(AVLNode* node) {
if (node == nullptr) {
return;
}
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
void destroyTree(AVLNode* node) {
if (node == nullptr) return;
destroyTree(node->left);
destroyTree(node->right);
delete node;
}
public:
AVLTree() : root(nullptr) {}
~AVLTree() {
destroyTree(root);
}
void insert(int key) {
root = insert(root, key);
}
bool search(int key) {
AVLNode* current = root;
while (current != nullptr) {
if (key == current->data) {
return true;
} else if (key < current->data) {
current = current->left;
} else {
current = current->right;
}
}
return false;
}
void display() {
cout << "AVL树中序遍历：";
inorder(root);
cout << endl;
}
};
int main() {
AVLTree avl;
// 插入节点
avl.insert(10);
avl.insert(20);
avl.insert(30);
avl.insert(5);
avl.insert(15);
avl.insert(25);
avl.insert(35);
avl.insert(3);
avl.insert(13);
avl.insert(23);
// 显示AVL树
avl.display();
// 查找
cout << "\n查找20: " << (avl.search(20) ? "找到" : "未找到") << endl;
cout << "查找30: " << (avl.search(30) ? "找到" : "未找到") << endl;
return 0;
}
💡 最佳实践¶
1. 查找算法选择¶
C++
// 查找算法选择
int main() {
// ✅ 好的做法：根据数据特点选择算法
// 有序数组：二分查找O(log n)
// 无序数组：线性查找O(n）
// 频繁查找：哈希表O(1)平均
// 需要范围查询：平衡树O(log n)
// ❌ 不好的做法：总是使用线性查找
// 总是使用线性查找（效率低）
// 不考虑数据特点（选择不合适）
return 0;
}
2. 哈希函数设计¶
C++
// 哈希函数设计
int main() {
// ✅ 好的做法：选择好的哈希函数
// 分布均匀
// 计算快速
// 冲突少
// ❌ 不好的做法：使用简单的哈希函数
// 总是使用key % size（分布不均）
// 不考虑冲突处理（效率低）
return 0;
}
📝 练习题¶
基础题¶
- 二分查找的时间复杂度是多少？
- 哈希表有哪些解决冲突的方法？
- 平衡树如何保持平衡？
进阶题¶
- 实现一个完整的哈希表。
- 实现红黑树。
- 优化查找算法性能。
实践题¶
- 创建一个简单的缓存系统。
- 实现一个索引结构。
- 构建一个高效的数据查询系统。
📚 推荐阅读¶
🔗 下一章¶
实战项目 - 通过一个完整的图书管理系统项目综合运用所学知识。