查找算法：顺序查找、二分查找、哈希查找、二叉搜索树
查找，说白了就是在一堆数据里找到你想要的那个。我做了这么多年开发，发现很多性能问题其实都出在查找上。你想想看，一个系统如果查找慢了，整个体验就崩了。今天咱们就把四种最核心的查找算法捋一遍。
顺序查找——最笨但最可靠
顺序查找的思路简单到令人发指：从头到尾，一个一个比。我刚开始学编程时，第一个写的查找代码就是这个。
// 顺序查找
int seq_search(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) return i;
}
return -1;
}时间复杂度O(n)，空间复杂度O(1)。没什么技巧，就是硬找。
我的经验：顺序查找最适合数据量小（比如几十个元素）或者数据无序的场景。我曾经在一个嵌入式项目里，数据总共就20个，用二分查找还得先排序，反而更慢。
二分查找——快，但有前提
二分查找的前提是数据必须有序。它的核心思想是：每次砍掉一半。
// 二分查找（迭代版）
int binary_search(int arr[], int n, int key) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key) return mid;
else if (arr[mid] < key) left = mid + 1;
else right = mid - 1;
}
return -1;
}时间复杂度O(log n)，空间复杂度O(1)。
注意：mid的计算用 left + (right - left) / 2 而不是 (left + right) / 2。为什么？因为left+right可能溢出。我曾经在面试题里见过这个坑，很多人没注意。
二分查找还有递归版本，不过我个人更推荐迭代版。递归虽然代码短，但函数调用有开销，而且容易栈溢出。
// 二分查找（递归版）
int binary_search_rec(int arr[], int left, int right, int key) {
if (left > right) return -1;
int mid = left + (right - left) / 2;
if (arr[mid] == key) return mid;
else if (arr[mid] < key)
return binary_search_rec(arr, mid + 1, right, key);
else
return binary_search_rec(arr, left, mid - 1, key);
}哈希查找——用空间换时间
哈希查找的核心是：通过一个哈希函数，直接把key映射到存储位置。理想情况下，时间复杂度O(1)。
但现实很骨感——哈希冲突是绕不开的问题。常用的解决方式有两种：
- 链地址法：每个哈希槽挂一个链表
- 开放地址法：冲突了就往后找空位
// 简单的哈希表（链地址法）
#define TABLE_SIZE 100
typedef struct Node {
int key;
int value;
struct Node* next;
} Node;
Node* hash_table[TABLE_SIZE];
int hash_func(int key) {
return key % TABLE_SIZE;
}
void insert(int key, int value) {
int index = hash_func(key);
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->key = key;
new_node->value = value;
new_node->next = hash_table[index];
hash_table[index] = new_node;
}
int search(int key) {
int index = hash_func(key);
Node* cur = hash_table[index];
while (cur) {
if (cur->key == key) return cur->value;
cur = cur->next;
}
return -1;
}核心要点：哈希函数的设计决定了查找效率。一个好的哈希函数应该让数据分布均匀，减少冲突。我常用的技巧是取模时用质数，比如用 10007 而不是 10000。
二叉搜索树——动态数据的利器
如果数据是动态插入删除的，二分查找就不太行了。这时候二叉搜索树（BST）就派上用场了。
BST的性质很简单：左子树所有节点小于根，右子树所有节点大于根。
// 二叉搜索树节点
typedef struct BSTNode {
int data;
struct BSTNode* left;
struct BSTNode* right;
} BSTNode;
// 插入
BSTNode* insert(BSTNode* root, int val) {
if (root == NULL) {
BSTNode* node = (BSTNode*)malloc(sizeof(BSTNode));
node->data = val;
node->left = node->right = NULL;
return node;
}
if (val < root->data)
root->left = insert(root->left, val);
else if (val > root->data)
root->right = insert(root->right, val);
return root;
}
// 查找
BSTNode* search(BSTNode* root, int key) {
if (root == NULL || root->data == key)
return root;
if (key < root->data)
return search(root->left, key);
else
return search(root->right, key);
}平均时间复杂度O(log n)，最坏情况O(n)——比如数据已经有序，BST就退化成链表了。
避坑指南：我曾经在一个项目里直接用BST存用户ID，结果用户注册是按顺序来的，树直接变成了一条线，查找慢得离谱。后来换成了平衡二叉树（AVL或红黑树）才解决问题。
四种算法对比
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 数据要求 |
|---|---|---|---|---|
| 顺序查找 | O(n) | O(n) | O(1) | 无 |
| 二分查找 | O(log n) | O(log n) | O(1) | 有序 |
| 哈希查找 | O(1) | O(n) | O(n) | 需哈希函数 |
| 二叉搜索树 | O(log n) | O(n) | O(n) | 可比较大小 |
知识体系总览
下面这张图把四种查找算法的关系梳理清楚了，你可以对照着看：
我的建议：实际开发中，别死磕一种算法。我经常是先用哈希表做快速查找，再用BST做范围查询，两者配合着用。记住，没有最好的算法，只有最合适的场景。
嗯，四种查找算法就讲到这里。代码我都跑过，可以直接用。如果你在实际项目中遇到查找性能问题，不妨回头看看这四种思路，总有一款适合你。