前言查找搜索是笔试、机试、面试核心考点分为静态查找数据集不变、动态查找支持增删两大类。 本文包含顺序查找、二分查找、分块查找、二叉搜索树、平衡二叉树 AVL、红黑树简述、哈希查找、跳表每种算法包含算法原理时间 / 空间复杂度优缺点与适用场景完整可运行 C 代码细节易错点说明一、静态查找无插入删除仅查询1. 顺序查找线性查找原理从头到尾逐个遍历数组逐个比对关键字找到返回下标遍历完无匹配返回 - 1。 支持无序数组、有序数组。复杂度最好 O (1)最坏 O (n)平均 O (n)空间 O (1)优缺点优点实现简单、不要求有序 缺点大数据量效率极低。C 实现cpp#include iostream #include vector using namespace std; // 顺序查找返回下标无则-1 int seqSearch(vectorint arr, int key) { for (int i 0; i arr.size(); i) { if (arr[i] key) { return i; } } return -1; } int main() { vectorint 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; }优化哨兵版减少循环判断cppint seqSearchGuard(vectorint 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. 二分查找折半查找仅有序数组原理数组升序每次取中间元素对比中间值 key命中中间值 key去右半区间查找中间值 key去左半区间查找复杂度平均 / 最坏 O (logn)空间迭代 O (1)、递归 O (logn)适用场景静态有序数组无频繁插入删除迭代版推荐无栈溢出cpp#include iostream #include vector using namespace std; int binarySearch(vectorint arr, int key) { int l 0, r arr.size() - 1; while (l r) { // 防止溢出等价 (lr)/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() { vectorint arr {1,2,3,4,5,6,7,8,9}; cout binarySearch(arr, 6) endl; return 0; }递归版二分cppint binaryRec(vectorint 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, mid1, r, key); else return binaryRec(arr, l, mid-1, key); }高频衍生题型代码查找左边界第一个等于 keycppint leftBound(vectorint 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; }查找右边界最后一个等于 keycpint rightBound(vectorint 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. 分块查找索引顺序查找原理数组分若干块块内无序、块间有序建立索引表存储每块最大值、块起始下标二分索引表确定目标块块内顺序查找。复杂度索引二分 O (logm) 块内顺序 O (s)m 块、块大小 sC 完整实现cpp#include iostream #include vector using namespace std; // 索引结构体 struct Index { int maxVal; int start; }; // 构建索引表 vectorIndex buildIndex(vectorint arr, int blockSize) { vectorIndex 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(vectorint arr, vectorIndex 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() { vectorint 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; // 哈希表数组链表 vectorlistint 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; vectorint 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. 跳表 SkipListRedis 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; vectorSkipNode* 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) { vectorSkipNode* 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; }三、所有查找算法对比汇总表格算法平均查找最坏查找插入删除是否有序适用场景顺序查找O(n)O(n)O(n)无序 / 有序少量数据、链表二分查找O(logn)O(logn)O(n)有序静态数组固定不变有序数组分块查找O(logms)O(logms)O(n)块间有序大数据静态表BSTO(logn)O(n)O(logn)动态有序小规模动态数据AVL 平衡树O(logn)O(logn)O(logn)动态有序频繁查改要求稳定复杂度哈希查找O(1)O(n)O(1)无序缓存、键值映射跳表O(logn)O(logn)O(logn)动态有序Redis 有序集合四、核心考点细节总结二分查找必须有序只适用于数组链表不能二分BST 退化根源有序数据连续插入平衡树解决该问题哈希查找优势是平均常数级但存在哈希冲突最坏退化AVL 平衡因子严格 ±1旋转多红黑树放宽平衡条件工业更常用跳表用多层链表替代平衡树无复杂旋转工程实现简单静态查找适合一次性构建、极少修改场景动态查找支持频繁增删。