数据结构查找算法大全

前言

查找（搜索）是笔试、机试、面试核心考点，分为静态查找（数据集不变）、动态查找（支持增删）两大类。 本文包含：顺序查找、二分查找、分块查找、二叉搜索树、平衡二叉树 AVL、红黑树（简述）、哈希查找、跳表，每种算法包含：

1. 算法原理
2. 时间 / 空间复杂度
3. 优缺点与适用场景
4. 完整可运行 C++ 代码
5. 细节易错点说明

一、静态查找（无插入删除，仅查询）

1. 顺序查找（线性查找）

原理

从头到尾逐个遍历数组，逐个比对关键字，找到返回下标，遍历完无匹配返回 - 1。 支持无序数组、有序数组。

复杂度

• 最好 O (1)，最坏 O (n)，平均 O (n)
• 空间 O (1)

优缺点

优点：实现简单、不要求有序； 缺点：大数据量效率极低。

C++ 实现

cpp

#include <iostream> #include <vector> using namespace std; // 顺序查找，返回下标，无则-1 int seqSearch(vector<int>& arr, int key) { for (int i = 0; i < arr.size(); i++) { if (arr[i] == key) { return i; } } return -1; } int main() { vector<int> arr = {5, 2, 9, 1, 5, 6}; int target = 9; int idx = seqSearch(arr, target); if (idx != -1) cout << "找到元素，下标：" << idx << endl; else cout << "未找到" << endl; return 0; }

优化哨兵版（减少循环判断）

cpp

int seqSearchGuard(vector<int>& arr, int key) { arr.push_back(key); // 末尾放哨兵 int i = 0; while (arr[i] != key) i++; arr.pop_back(); return i == arr.size() ? -1 : i; }

2. 二分查找（折半查找，仅有序数组）

原理

数组升序，每次取中间元素对比：

1. 中间值 == key：命中
2. 中间值 < key：去右半区间查找
3. 中间值 > key：去左半区间查找

复杂度

平均 / 最坏 O (logn)，空间迭代 O (1)、递归 O (logn)

适用场景

静态有序数组，无频繁插入删除

迭代版（推荐，无栈溢出）

cpp

#include <iostream> #include <vector> using namespace std; int binarySearch(vector<int>& arr, int key) { int l = 0, r = arr.size() - 1; while (l <= r) { // 防止溢出，等价 (l+r)/2 int mid = l + (r - l) / 2; if (arr[mid] == key) return mid; else if (arr[mid] < key) l = mid + 1; else r = mid - 1; } return -1; } int main() { vector<int> arr = {1,2,3,4,5,6,7,8,9}; cout << binarySearch(arr, 6) << endl; return 0; }

递归版二分

cpp

int binaryRec(vector<int>& arr, int l, int r, int key) { if (l > r) return -1; int mid = l + (r - l) / 2; if (arr[mid] == key) return mid; else if (arr[mid] < key) return binaryRec(arr, mid+1, r, key); else return binaryRec(arr, l, mid-1, key); }

高频衍生题型代码

1. 查找左边界（第一个等于 key）

cpp

int leftBound(vector<int>& arr, int key) { int l = 0, r = arr.size()-1; int ans = -1; while(l <= r) { int mid = l + (r-l)/2; if(arr[mid] == key) { ans = mid; r = mid - 1; } else if(arr[mid] < key) l = mid + 1; else r = mid - 1; } return ans; }

1. 查找右边界（最后一个等于 key）

cp

int rightBound(vector<int>& arr, int key) { int l = 0, r = arr.size()-1; int ans = -1; while(l <= r) { int mid = l + (r-l)/2; if(arr[mid] == key) { ans = mid; l = mid + 1; } else if(arr[mid] < key) l = mid + 1; else r = mid - 1; } return ans; }

3. 分块查找（索引顺序查找）

原理

1. 数组分若干块，块内无序、块间有序；
2. 建立索引表：存储每块最大值、块起始下标；
3. 二分索引表确定目标块，块内顺序查找。

复杂度

索引二分 O (logm) + 块内顺序 O (s)，m 块、块大小 s

C++ 完整实现

cpp

#include <iostream> #include <vector> using namespace std; // 索引结构体 struct Index { int maxVal; int start; }; // 构建索引表 vector<Index> buildIndex(vector<int>& arr, int blockSize) { vector<Index> idx; int n = arr.size(); for (int i = 0; i < n; i += blockSize) { Index tmp; tmp.start = i; int maxx = arr[i]; int end = min(i + blockSize, n); for (int j = i; j < end; j++) maxx = max(maxx, arr[j]); tmp.maxVal = maxx; idx.push_back(tmp); } return idx; } int blockSearch(vector<int>& arr, vector<Index>& idx, int blockSize, int key) { // 二分索引找块 int l = 0, r = idx.size()-1; int targetBlock = -1; while(l <= r) { int mid = l + (r-l)/2; if(idx[mid].maxVal >= key) { targetBlock = mid; r = mid - 1; } else { l = mid + 1; } } if(targetBlock == -1) return -1; // 块内顺序查找 int start = idx[targetBlock].start; int end = min(start + blockSize, (int)arr.size()); for(int i = start; i < end; i++) { if(arr[i] == key) return i; } return -1; } int main() { vector<int> arr = {22,12,13,8,20,33,42,44,38,24,48,60,58,74,49}; int block = 5; auto idx = buildIndex(arr, block); cout << blockSearch(arr, idx, block, 44) << endl; return 0; }

二、动态查找（支持增、删、查，数据集可变）

4. 二叉搜索树 BST

性质

左子树所有节点 < 根 < 右子树所有节点；中序遍历升序。

复杂度

平衡时 O (logn)，极端有序数据退化成链表 O (n)

C++ 完整实现（增删查）

cpp

#include <iostream> using namespace std; struct BSTNode { int val; BSTNode* left; BSTNode* right; BSTNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 查找 BSTNode* bstSearch(BSTNode* root, int key) { if (!root || root->val == key) return root; if (key < root->val) return bstSearch(root->left, key); else return bstSearch(root->right, key); } // 插入 BSTNode* bstInsert(BSTNode* root, int key) { if (!root) return new BSTNode(key); if (key < root->val) root->left = bstInsert(root->left, key); else if (key > root->val) root->right = bstInsert(root->right, key); return root; } // 找最小值节点（删除用） BSTNode* getMin(BSTNode* root) { while (root->left) root = root->left; return root; } // 删除节点 BSTNode* bstDelete(BSTNode* root, int key) { if (!root) return nullptr; if (key < root->val) root->left = bstDelete(root->left, key); else if (key > root->val) root->right = bstDelete(root->right, key); else { // 找到待删节点 // 情况1：叶子 / 单孩子 if (!root->left) { BSTNode* tmp = root->right; delete root; return tmp; } if (!root->right) { BSTNode* tmp = root->left; delete root; return tmp; } // 情况2：左右都有，取右子树最小替换 BSTNode* minRight = getMin(root->right); root->val = minRight->val; root->right = bstDelete(root->right, minRight->val); } return root; } // 中序遍历 void inOrder(BSTNode* root) { if (!root) return; inOrder(root->left); cout << root->val << " "; inOrder(root->right); } int main() { BSTNode* root = nullptr; root = bstInsert(root,5); root = bstInsert(root,3); root = bstInsert(root,7); root = bstInsert(root,1); root = bstInsert(root,4); inOrder(root); cout << endl; root = bstDelete(root,3); inOrder(root); return 0; }

5. AVL 平衡二叉树（自平衡 BST）

核心规则

任意节点左右子树高度差（平衡因子）绝对值≤1；插入 / 删除失衡通过旋转恢复平衡。 旋转类型：LL、RR、LR、RL。

C++ 完整实现（增、查、旋转）

cpp运行

#include <iostream> #include <algorithm> using namespace std; struct AVLNode { int val; int height; AVLNode* left; AVLNode* right; AVLNode(int x) : val(x), height(1), left(nullptr), right(nullptr) {} }; int getHeight(AVLNode* root) { return root ? root->height : 0; } int getBalance(AVLNode* root) { return getHeight(root->left) - getHeight(root->right); } // 右旋 LL AVLNode* rightRotate(AVLNode* y) { AVLNode* x = y->left; AVLNode* T = x->right; x->right = y; y->left = T; y->height = 1 + max(getHeight(y->left), getHeight(y->right)); x->height = 1 + max(getHeight(x->left), getHeight(x->right)); return x; } // 左旋 RR AVLNode* leftRotate(AVLNode* x) { AVLNode* y = x->right; AVLNode* T = y->left; y->left = x; x->right = T; x->height = 1 + max(getHeight(x->left), getHeight(x->right)); y->height = 1 + max(getHeight(y->left), getHeight(y->right)); return y; } // 插入 AVLNode* avlInsert(AVLNode* root, int key) { if (!root) return new AVLNode(key); if (key < root->val) root->left = avlInsert(root->left, key); else if (key > root->val) root->right = avlInsert(root->right, key); else return root; root->height = 1 + max(getHeight(root->left), getHeight(root->right)); int bal = getBalance(root); // LL if (bal > 1 && key < root->left->val) return rightRotate(root); // RR if (bal < -1 && key > root->right->val) return leftRotate(root); // LR if (bal > 1 && key > root->left->val) { root->left = leftRotate(root->left); return rightRotate(root); } // RL if (bal < -1 && key < root->right->val) { root->right = rightRotate(root->right); return leftRotate(root); } return root; } AVLNode* avlSearch(AVLNode* root, int key) { if (!root || root->val == key) return root; if (key < root->val) return avlSearch(root->left, key); return avlSearch(root->right, key); } void inOrder(AVLNode* root) { if (!root) return; inOrder(root->left); cout << root->val << " "; inOrder(root->right); } int main() { AVLNode* root = nullptr; int arr[] = {10,20,30,40,50,25}; for (int x : arr) root = avlInsert(root, x); inOrder(root); return 0; }

6. 哈希查找（散列查找，平均 O (1)）

原理

哈希函数映射关键字到数组下标；冲突解决：链地址法、开放寻址。

方案 1：链地址法（C++ 实现，推荐）

cpp

#include <iostream> #include <vector> #include <list> using namespace std; const int MOD = 10; // 哈希表：数组+链表 vector<list<int>> hashTable(MOD); // 哈希函数 int hashFunc(int key) { return key % MOD; } // 插入 void hashInsert(int key) { int idx = hashFunc(key); hashTable[idx].push_back(key); } // 查找 bool hashSearch(int key) { int idx = hashFunc(key); for (int num : hashTable[idx]) { if (num == key) return true; } return false; } // 删除 void hashRemove(int key) { int idx = hashFunc(key); hashTable[idx].remove(key); } int main() { hashInsert(12); hashInsert(22); hashInsert(35); cout << boolalpha << hashSearch(22) << endl; hashRemove(22); cout << hashSearch(22) << endl; return 0; }

方案 2：开放寻址法（线性探测）

cpp

#include <iostream> #include <vector> using namespace std; const int SIZE = 15; const int EMPTY = -1; vector<int> hashTable(SIZE, EMPTY); int hashFunc(int k) { return k % SIZE; } void insert(int key) { int idx = hashFunc(key); while (hashTable[idx] != EMPTY) { idx = (idx + 1) % SIZE; } hashTable[idx] = key; } bool search(int key) { int idx = hashFunc(key); int start = idx; while (hashTable[idx] != EMPTY) { if (hashTable[idx] == key) return true; idx = (idx + 1) % SIZE; if (idx == start) break; } return false; }

7. 跳表 SkipList（Redis ZSet 底层）

原理

多层有序链表，上层作为索引加速查找，平均 O (logn)；无需平衡旋转，实现比 AVL / 红黑树简单。 简化 C++ 极简实现：

cpp

#include <iostream> #include <vector> #include <cstdlib> #include <ctime> using namespace std; #define MAX_LEVEL 5 struct SkipNode { int val; vector<SkipNode*> next; SkipNode(int v, int level) : val(v), next(level, nullptr) {} }; class SkipList { private: SkipNode* head; int curLevel; // 随机层数 int randomLevel() { int lvl = 1; while (rand() % 2 == 0 && lvl < MAX_LEVEL) lvl++; return lvl; } public: SkipList() { srand((unsigned)time(NULL)); head = new SkipNode(-1, MAX_LEVEL); curLevel = 1; } // 查找 bool search(int key) { SkipNode* p = head; for (int i = curLevel - 1; i >= 0; i--) { while (p->next[i] && p->next[i]->val < key) p = p->next[i]; } p = p->next[0]; return p && p->val == key; } // 插入 void insert(int key) { vector<SkipNode*> update(MAX_LEVEL, nullptr); SkipNode* p = head; for (int i = curLevel - 1; i >= 0; i--) { while (p->next[i] && p->next[i]->val < key) p = p->next[i]; update[i] = p; } int newLvl = randomLevel(); SkipNode* newNode = new SkipNode(key, newLvl); for (int i = 0; i < newLvl; i++) { newNode->next[i] = update[i]->next[i]; update[i]->next[i] = newNode; } if (newLvl > curLevel) curLevel = newLvl; } }; int main() { SkipList sl; sl.insert(3); sl.insert(1); sl.insert(5); cout << boolalpha << sl.search(3) << endl; return 0; }

三、所有查找算法对比汇总

表格

四、核心考点细节总结

1. 二分查找必须有序，只适用于数组，链表不能二分；
2. BST 退化根源：有序数据连续插入，平衡树解决该问题；
3. 哈希查找优势是平均常数级，但存在哈希冲突最坏退化；
4. AVL 平衡因子严格 ±1，旋转多；红黑树放宽平衡条件，工业更常用；
5. 跳表用多层链表替代平衡树，无复杂旋转，工程实现简单；
6. 静态查找适合一次性构建、极少修改场景；动态查找支持频繁增删。