顺序查找、二分查找、哈希查找这几个词在C语言学习里出现的频率差不多和printf(hello world)一样高。但说句实话很多人学完这些算法能在考试里算出时间复杂度却在真正写代码时不知道该用哪个。更常见的情况是明明用了二分查找数据量稍微一大就出问题或者明明数据规模很小非得上一个哈希表重写一堆代码最后性能提升几乎可以忽略。我写这篇东西的出发点很简单。做了这么多年C语言相关的开发也带过不少新人我发现查找算法这块的认知断层最严重。教材讲原理面试问八股但到了实际项目里尤其是涉及嵌入式、底层系统、性能敏感模块时很多人就懵了。这篇文章不打算像教科书那样把每种算法念一遍而是把顺序查找、二分查找、分块查找、哈希查找、二叉搜索树这几类常见的方案放在一起用同一组数据、同一个场景去做对比把它们的选型逻辑、边界条件、内存开销、甚至常见Bug都拆开讲清楚。不管你是刚学完C语言基础、正在刷题的学生还是已经工作、需要在实际项目里做数据检索的开发者这篇文章应该都能给你一些参考。我会尽量把话讲得直白一点复杂的地方用实际例子和代码说话。1. 查找算法为什么值得单独拿出来对比1.1 先搞清楚一个问题查找到底在解决什么查找的本质是从一组数据里找到满足特定条件的元素。听起来简单但真正做起来难点从来不在“找到”而在“多快找到”和“在什么条件下能找到”。举个很生活化的例子。你在一个没有目录的文档里找一个关键词只能从头往后翻这是顺序查找。如果文档有目录而且内容按字母顺序排好你直接翻到大概的位置再根据前后页判断往前还是往后这就是二分查找的思路。如果文档建了一个索引表每个关键词对应一个页码你查索引一下就定位了这就是哈希查找的雏形。如果文档是一个多层级的目录结构每级目录下面还有子目录那这就是树形查找的思路。C语言里实现这些查找算法本质上就是在内存里管理一块连续数组、一段链表或者一个树结构然后根据不同的组织方式选择合适的搜索策略。这里必须强调一个核心观点查找算法的效率很大程度上不取决于算法本身而取决于数据结构怎么组织。二分查找之所以快前提是数据有序且能随机访问哈希查找之所以快前提是你设计了一个好的哈希函数并且冲突处理得当。你在一个无序数组里用二分查找那是错的你在一组字符串上直接比较哈希值那也是错的。1.2 算法选型前必须先想清楚的三件事在实际做技术选型的时候我不会先翻书查算法复杂度而是先问自己三个问题第一数据量有多大100个元素的数组和1000万个元素的数组完全是两个量级的问题。100个元素顺序查找可能比二分查找更快原因是二分查找的循环跳转和比较分支会破坏CPU的流水线这个微观层面的开销在小规模数据下反而更明显。但1000万条记录顺序查找就完全不可接受了。第二数据是静态的还是动态的如果数据在程序运行期间基本不变比如一个配置表、一个常量字典那么排序一次之后用二分查找或者干脆建一个完美的哈希表都是非常好的方案。但如果数据频繁插入、删除那维护有序数组的代价会很高——每次插入都要搬移后面的元素这时候二叉搜索树、跳表这类可动态调整的结构就更有优势。第三有没有额外内存可以用哈希表需要额外的桶数组而且为了减少冲突桶的数量通常是数据量的1.5倍到2倍这在PC上无所谓但在单片机或者内存受限的嵌入式环境里可能就是致命的。分块查找的索引表开销不大但前提是你对数据的分布规律有把握。这三个问题想清楚了查找算法的选择就不难了。接下来我详细拆解几种典型算法的实现要点和实际表现。1.3 准备工作建立一个可对比的测试环境在对比分析之前我先说一下这篇文章里所有测试样例的统一环境。我用的是一台普通的x86 Linux机器编译器是GCC 9.4编译选项用了-O2。测试数据是10万个随机生成的32位无符号整数范围限制在0到100万之间。这样设计的原因是数据量不至于太小看不出差异又不会大到需要引入外存或复杂内存管理干扰算法本身的对比。同时我会准备三组数据形态一组是无序数组一组是有序数组一组是接近有序但偶尔有逆序的情况。这样做的目的是为了观察同一个算法在不同数据形态下的表现差异。说实话很多人在算法分析时只看时间复杂度忽略了数据的初始状态这在工程上是个大坑。我会在后面的测试结果里专门展开这点。#include stdio.h #include stdlib.h #include time.h #define DATASIZE 100000 #define MAXVALUE 1000000 int cmp_uint(const void *a, const void *b) { return (*(unsigned int *)a *(unsigned int *)b) - (*(unsigned int *)a *(unsigned int *)b); } int main(void) { unsigned int data[DATASIZE]; srand((unsigned)time(NULL)); for (int i 0; i DATASIZE; i) { data[i] rand() % MAXVALUE; } // 记录无序态再排序 unsigned int unsorted[DATASIZE]; memcpy(unsorted, data, sizeof(data)); qsort(data, DATASIZE, sizeof(unsigned int), cmp_uint); // 后续测试分别在 unsorted 和 data 上进行 return 0; }这段代码是后面所有测试的公共前置部分。先定义数据规模生成随机数据保留一份无序拷贝再对另一份做排序。后续每个算法测试函数都基于这两份数组展开保证对比公平。注意到我这里比较函数没有写成return *(unsigned int *)a - *(unsigned int *)b;因为当差值超出int范围时会溢出。虽然这里取值比较小不会遇到但养成好习惯用逻辑运算规避溢出问题。2. 最基础的两个选手顺序查找与二分查找2.1 顺序查找简单但没那么简单的O(n)顺序查找的代码我不用写大家都会。一个循环从数组头查到尾匹配到了就返回下标查完了没找到就返回-1。但正是因为它简单反而容易被忽视一些细节。首先是一个优化点哨兵法。普通的顺序查找每次循环都要判断i n和arr[i] target两个条件。哨兵法把目标值放到数组末尾作为哨兵然后只用一个循环判断arr[i] ! target命中哨兵位置时退出循环再判断是否越界。这样减少了每次循环的分支数量数据量大时能有一点性能提升。int seq_search_sentinel(unsigned int *arr, int n, unsigned int target) { int i 0; unsigned int last arr[n - 1]; arr[n - 1] target; // 放置哨兵 while (arr[i] ! target) { i; } arr[n - 1] last; // 恢复末尾数据 if (i n - 1) { return i; } if (last target) { return n - 1; } return -1; }这里有个坑如果目标值恰好就是数组末尾原本的值哨兵位置和目标值相同循环会在n-1处停下此时无法区分是找到了还是哨兵生效。所以必须加那段恢复和最终判断的逻辑先恢复末尾数据再继续判断。我见过不少人在笔试里写哨兵法结果因为这个边界条件处理不对而丢分。顺序查找的时间复杂度是O(n)这个没有争议。但实际测试中我发现一个问题在-O2编译优化下如果数据恰好是均匀随机分布的CPU的分支预测器通常能猜中“未命中”的分支所以实际的查找速度比理论上看起来要快很多。10万个数据里找一个存在值在末尾位置附近找到时大约需要几毫秒级别但如果数据无序、目标又不存在就老老实实遍历全部数据这时性能瓶颈完全体现在内存访问上。2.2 二分查找边界条件是所有Bug的温床二分查找这个算法理论上很优雅每次排除一半数据时间复杂度O(log n)。我在实际面试中问过不少候选人能一次写对二分查找的人比例远低于预期。最常见的坑集中在几个地方循环条件是left right还是left right更新left和right时mid本身是否需要跳过用(left right) / 2时会不会整数溢出。关于溢出这个点很多C语言教材上还写着mid (left right) / 2这在大多数情况下没问题但一旦left right超过了int的最大值就会溢出变成负数之后的行为就完全不可预测了。标准的写法是mid left (right - left) / 2这个写法在数据量大的时候很关键。我在测试程序里数据规模固定在10万不会触发溢出但这个习惯一定要养成。int binary_search(unsigned int *arr, int n, unsigned int target) { int left 0; int right n - 1; int mid; while (left right) { 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; }这段代码用left right作为循环条件区间是闭区间。找到就直接返回否则根据中间值和目标值的大小关系收缩左边界或右边界。我用left mid 1和right mid - 1保证每次循环都能真正收缩区间。如果用left right那你需要额外记住退出循环后还要再做一次判断而且很容易在只剩一个元素时陷入死循环。二分查找的前提是数据有序这个说得太多就不重复了。但有一个很多人没意识到的问题二分查找对有序数组的“随机访问”要求在连续内存的数组里表现最好。如果是链表即使链表已经排序也没法用二分查找——因为你要快速访问中间元素链表做不到O(1)的随机访问。这就是为什么在很多C语言面试题里链表相关的查找题往往不会要求二分思路而是转向快慢指针之类的技巧。2.3 小规模数据下到底选谁我实测过一个很有意思的情况在数据量小于64个元素时二分查找的速度优势并不明显有时候甚至更慢。原因在于顺序查找非常符合CPU的流水线分支预测模式而二分查找的跳转是随机的每次arr[mid]的地址都不同会导致缓存行频繁切换。当然这不是说小数据就该用顺序查找工程上的最优策略往往是“阈值判断”。比如很多标准库里的排序实现当待排序区间小于某个阈值时会切换成插入排序。查找也一样我们可以写一个混合查找数据量小直接用顺序查找数据量大再走二分查找。这个阈值需要实测不同的CPU、不同的编译器优化级别最优值都不一样通常我在x86上取16到32之间。3. 工程里更常见的分块查找与哈希查找3.1 分块查找顺序与二分之间的一种折中分块查找很多教材里讲得不多但它在真实项目里其实很有用尤其在嵌入式环境、内存受限、数据量中等的情况下。分块查找的思想是先把数据分成若干块块内不一定有序但块与块之间有大小关系。或者反过来说块内严格有序块间保持“每一块的最大值小于下一块的最小值”。这样你可以先对“块索引表”二分查找确定目标可能在哪个块再进块内顺序查找。为什么这种方案实用因为它兼顾了空间和性能。索引表的大小只有块数量通常几十到几百个元素内存开销很小。而块内顺序查找虽然最坏还是O(n)但如果你把块大小控制得当比如每块256个元素那最坏也就256次比较完全可以接受。typedef struct { unsigned int max_value; int start_index; int count; } block_index_t; int block_search(unsigned int *arr, int n, int block_size, unsigned int target, block_index_t *idx, int idx_len) { int block_pos -1; // 在索引表中二分查找找到第一个max_value target的块 int left 0; int right idx_len - 1; while (left right) { int mid left (right - left) / 2; if (idx[mid].max_value target) { block_pos mid; right mid - 1; } else { left mid 1; } } if (block_pos -1) { return -1; // 所有块最大值都小于target } int start idx[block_pos].start_index; int count idx[block_pos].count; for (int i start; i start count; i) { if (arr[i] target) { return i; } } return -1; }这里我先在索引表上做二分查找找的是“第一个最大值不小于目标值的块”这样如果目标值存在一定落在这个块里如果上一块的最大值比目标小那目标不可能在上一块。这一步很关键二分查找时要清楚地定义“找到什么”找不到精确值时找的是下界。如果找的是上界逻辑就反了。分块查找有个前置条件你要能预先确定每个块的边界并且块与块之间有顺序关系。如果一个块里的最大值比下一块的最小值还大那这个分块索引就失效了。在实际项目里我通常会在插入数据时就维护好分块结构或者对静态数据先排序再分块。这个算法的可读性比纯二分好而且灵活度更高——比如你的数据是非均匀分布的可以把高频区域切成小块的密集块低频区域切成大块用“变长分块”优化命中率。3.2 哈希查找用空间换时间的极限哈希查找的核心是设计一个哈希函数把关键字映射到一个数组下标上理想情况下O(1)直接定位。C语言本身不提供哈希表的标准库POSIX里有hsearch但功能极其有限所以大多数时候你得自己实现一个或者从开源库拉一个。这个过程里最关键的是哈希函数和冲突处理策略。我自己的经验是不要在一开始就追求什么MFC、FNV这类复杂哈希除非你能证明你的数据分布有问题否则最简单的取模运算就行。哈希函数“好不好”的判断标准是不同的输入映射到同一个桶的概率是否趋近于随机分布。如果你的数据本身是均匀的随机整数key % size已经非常好。#define TABLE_SIZE 200003 // 用一个大质数做桶数 typedef struct entry { unsigned int key; int value; // 可以存下标或者其他附加信息 struct entry *next; } entry_t; entry_t *hash_table[TABLE_SIZE]; unsigned int hash_func(unsigned int key) { return key % TABLE_SIZE; } void insert_entry(unsigned int key, int value) { unsigned int idx hash_func(key); entry_t *e (entry_t *)malloc(sizeof(entry_t)); e-key key; e-value value; e-next hash_table[idx]; hash_table[idx] e; } int search_entry(unsigned int key) { unsigned int idx hash_func(key); entry_t *e hash_table[idx]; while (e ! NULL) { if (e-key key) { return e-value; } e e-next; } return -1; }这里桶数选了一个质数200003比数据量10万的两倍略多一点。别小看这个细节如果桶数取100000而数据恰好集中在能被100000整除的key上那所有数据会挤在少数几个桶里查找效率直接退化成链表遍历。用质数可以减少这种“模式化映射”的风险因为你实际数据的规律一般是未知的质数模运算能把这些隐藏规律打散。哈希表的查找时间复杂度理想是O(1)但最坏情况是O(n)——所有key都哈希到同一个桶退化成链表。我实测过在桶数为2倍数据量、哈希函数取模的情况下每个桶的平均链表长度大概在0.5左右查找一个存在的key平均只需要1到2次比较速度几乎可以忽略不计。但如果你的哈希函数设计得差或者桶数太少性能衰退是断崖式的从毫秒级直接跳到几十毫秒。3.3 哈希冲突处理实测经验哈希冲突有两大类常见处理方案链地址法开散列和开放寻址法闭散列。链地址法就是上面代码里那样每个桶后面挂一个链表。开放寻址法则是当位置被占用时按某种探测序列去找下一个空位。链地址法实现简单、删除容易但每个节点要存一个指针内存开销大。开放寻址法不需要指针但删除节点不能直接删除否则会打断探测链需要打一个“已删除”标记。在C语言项目里我见过不少人直接用链地址法因为写起来方便。但如果你在内存受限的单片机环境链地址法里那个next指针的成本就不能忽视了——每个节点多4个字节32位机器10万个节点就多40万个字节。这时候开放寻址法反而是更经济的选择虽然探测序列会带来额外的比较。这个取舍没有绝对的优劣看场景。还有一个小技巧如果你知道所有要插入的key集合可以预先计算每个哈希值手工挑一个哈希函数和桶数让冲突数逼近于0这就是“完美哈希”的思路。在静态字典、关键字表这种场景下完美哈希能省下大量的运行时开销。但实际项目的key集合通常是动态的这个技巧使用场景有限不过知道有这回事面试时能加分不少。4. 链式结构与二叉搜索树C语言里的“动态查找”4.1 链表查找和指针操作要配合好热词里有一个“c语言 链表”说明不少人对链表查找也有困惑。链表查找本身没什么特别之处从头指针开始逐个往后遍历比较节点里的数据域找到返回找不到到尾部结束。它和数组的顺序查找复杂度一样是O(n)但常数更大因为每次移动都要靠node node-next指针跳转而数组是直接i访问连续内存缓存对数组更友好。链表查找真正有意思的地方在于和“有序性”结合。一个有序单链表查找仍然是O(n)因为哪怕你知道要找的数排在第几个位置还是得从头走过去。这个时候如果查找频率很高插入删除频率也高那应该考虑跳表。跳表本质是“多级链表”每一层跳跃的步长更大查找时可以快速跳过大量节点。C语言里手写一个跳表大概要200行比二叉搜索树繁琐但它的局部性更好、实现无递归不少追求稳定性的项目里反而更偏好跳表。这里我想提一个很多新手会犯的错误用字符串作为链表节点里的数据时比较要用strcmp不能直接写if (node-name target)。后者比较的是指针地址不是字符串内容。如果两个字符串内容相同但存储地址不同这个判断永远不成立。4.2 二叉搜索树C语言数据结构课的重头戏二叉搜索树BST的查找逻辑很直观从根开始目标值比当前节点小就往左走比当前节点大就往右走相等就命中。平均复杂度O(log n)但前提是树保持平衡。C语言实现时每个节点包含数据域、左孩子指针、右孩子指针结构体定义如下typedef struct bst_node { unsigned int key; struct bst_node *left; struct bst_node *right; } bst_node_t; bst_node_t *bst_search(bst_node_t *root, unsigned int target) { while (root ! NULL) { if (target root-key) { return root; } else if (target root-key) { root root-left; } else { root root-right; } } return NULL; }注意我这里用了循环而不是递归。理论上递归写起来更简洁但C语言的递归调用有函数栈开销而且深度过大会有栈溢出风险。在嵌入式或者长时间运行的服务端任务里我不会用递归去遍历一棵深度可能很深的树。这个“不用递归”的习惯也是我看热词里“单片机c语言没有堆栈吗为什么”这条之后想单独强调的。4.3 平衡问题与退化风险二叉搜索树最大的风险是退化。如果你按顺序插入1、2、3、4、5那么整棵树会退化成一个只有右子树的“链表”查找复杂度直接变成O(n)。避免这个问题有两条路一是在插入时做旋转维持平衡这就是AVL树和红黑树二是用随机化手段比如跳表的随机层数就是这个思路。红黑树在C语言里实现代码量不小但Linux内核的运行时调度器里就用了红黑树可见它在动态数据场景下的价值。如果你只是做一个学习项目写一棵平衡二叉搜索树确实能磨炼指针操作能力但如果你在开发实际项目我要说句实话真到了需要自平衡树的时候直接找一个成熟的实现或者用跳表比自己手写红黑树要稳妥得多。手写平衡树在插入、删除时稍有不慎就会破坏旋转逻辑这种Bug非常难排查往往只在特定数据序列下才复现。5. 嵌入式场景下的查找单片机C语言注意事项5.1 没有栈就没有递归吗热词里有一条“单片机c语言没有堆栈吗为什么”这个问题值得认真回答一下。单片机的C语言环境当然有堆栈——函数调用、局部变量、返回地址都需要栈的支持。但单片机里的栈空间通常非常小比如一个STM32工程链接脚本里分配的栈可能只有4KB到8KB而PC上Linux默认进程栈限制往往是8MB差距上千倍。这带来的直接影响是递归函数在单片机上非常危险。一个二叉搜索树的递归查找如果树深达到几百层每次递归都要消耗几十字节栈空间几KB的栈很快就被吃光了然后就是栈溢出程序跑飞。所以嵌入式C代码里但凡能用循环解决的问题就不要用递归查找算法更是如此。这也是为什么上面写BST查找时我给的例子是循环版本而不是递归版本。5.2 堆栈限制下的查找算法选型在单片机上做查找有两个额外约束RAM小、CPU主频低。我在一个基于ARM Cortex-M3的项目里需要在几百条配置记录里做按ID查找记录是静态的、在Flash里存放的。当时我评估了几个方案顺序查找最简单每条记录从头到尾比最坏情况要几百次比较每次都要读Flash以72MHz的主频来说一次查找大概要几微秒完全够用而且Flash的读取速度虽然比RAM慢但几百个字节的顺序读并不会成为瓶颈。二分查找理论上更优但前提是记录按ID排好序。如果ID排序是天然成立的比如写在配置文件里的ID本来就是递增的那二分查找确实能把比较次数从几百降到十次以内。但要注意二分查找每次都要随机跳过一段距离读FlashFlash的随机读取效率不高数据跨页时性能反而退化。哈希查找在单片机上要特别谨慎。哈希表需要一个较大的桶数组RAM吃不消。有的项目退而求其次在Flash里放一个提前算好的静态哈希表这倒是可行但要保证Flash空间够用且哈希函数在编译期就能确定。我的结论是在嵌入式环境里除非性能真的不够优先选择顺序查找或分块查找它们的代码简单、内存占用小、行为可预测最重要的是不怕栈溢出和随机读性能退化。单片机上“看起来更高级”的算法往往因为资源限制而发挥不出理论上的优势。5.3 静态查找表嵌入式里的“秘密武器”嵌入式开发里还有一种很常见但教材很少提的查找方式直接用静态查找表。既然数据是固定的那不如在编译期间就把数据组织好烧录到Flash里运行时不产生任何动态内存分配。比如按键码到功能码的映射表、传感器校准参数表都可以用const数组或者const结构体数组定义。查这种静态表时可以用编译器帮你优化的技巧如果表的长度不是很长把查找函数写成一长串简单的比较语句编译器往往能生成二分跳转或者查表指令比你在运行时做的二分查找还快。这在PC上没多大用但在单片机这种小代码库里往往能省下不少CPU周期。6. 查找算法的性能对比测试与排查技巧6.1 一组可复现的对比数据我基于前面说的10万条随机数据对顺序查找、二分查找、分块查找、哈希查找做了一组简单的计时测试。测试目标固定在有序数组中查找10000次每次查找的key从另一个随机数组中取值保证有一部分命中、一部分不命中。计时方式用clock_gettime(CLOCK_MONOTONIC)循环多次取平均值。测试结果大致如下具体数值会因机器而异但相对关系基本稳定查找算法数据状态查找10000次平均耗时时间复杂度额外内存需求顺序查找无序约50毫秒O(n)无顺序查找哨兵优化无序约45毫秒O(n)无二分查找有序约1毫秒O(log n)无分块查找分块有序约3毫秒O(sqrt(n))~O(log n)索引表哈希查找链地址法无要求约0.05毫秒O(1)平均桶数组链表节点看到这个数据可能有人会觉得那无脑用哈希不就行了但是要注意哈希表把10万个数据全部插入需要额外构建时间这里没有算进去。如果只在程序里查找几次构建哈希表的时间可能比查找本身还长得不偿失。这个“构建开销”在做算法选型时经常被忽略但它才是很多性能问题的真正来源。在有序数组上二分查找一个key只需要约17次比较因为2^17 13107210000次查找约17万次比较所以1毫秒的耗时是合理的。哈希查找平均每次只需要1到2次比较10000次查找大约几万次指针访问0.05毫秒这个量级也符合预期。6.2 常见Bug排查实录字节序和大小端问题在嵌入式环境里做哈希查找时如果你把一个int类型的数据通过memcpy转成字节数组再计算哈希那不同大小端机器得到的哈希值会不一样。这个问题在PC上测不出来但换到ARM单片机上就翻车。排查方法是规范化字节序或者在协议层就定义好哈希函数只接受统一的字节序。二分查找死循环死循环的根源通常是区间收缩时没有真正变小。我之前写过left mid而不是left mid 1在left和right相邻时mid会一直等于left然后left又等于mid就永远卡在同一个区间里。调试这类问题我习惯在循环里加一个printf打印left、right、mid的值看它们每次怎么变化。哈希表桶数选择不当这个问题我前面提到过凑合选一个100000的桶数如果数据是等差数列比如key都是100000的倍数那哈希就全映射到桶0上。排查方法是打印每个桶的链表长度如果发现某个桶特别长而大多数桶是空的那就是哈希函数或桶数没选好。调桶数为质数之后问题基本能解决。strstr()能否查找二进制内存这也是热词里的一个点。strstr按字符串查找遇到\0就停所以你用它去查找包含\0的二进制块结果一定是错的。正确做法是用memmem函数或者自己写一个基于memcmp的字节序列匹配。这个问题在C语言开发里经常出现尤其是在解析协议栈、处理文件结构时。6.3 内存碎片与生命周期问题在用链地址法实现哈希表时每个节点都单独malloc插入10万条数据就会产生10万次小内存分配。在PC上没问题但在长时间运行的服务端程序里频繁的小块分配释放会导致内存碎片。我见过一个真实案例服务跑了两周后哈希表查找越来越慢排查半天发现是内存碎片导致malloc变慢缓存命中率大幅下降。解决方案有几种一是用内存池预先分配一大块内存然后从池里按节点大小切分二是用开放寻址法把哈希表做成一个大数组插入时直接写入数组元素避免链表节点的动态分配三是定期重建哈希表把旧数据重新插入到新桶数组里顺便清理碎片。具体用哪种要根据项目的容错能力和维护成本来衡量。7. 查找算法从理论到落地几个值得记住的经验写了这么多最后我想把自己在实际写C语言代码时的一些体会分享一下。这些不是教科书里的标准答案但都是我踩过坑之后总结出来的。第一点排序是二分查找最好的朋友也是最大的敌人。二分查找快前提是数据有序。但“维护有序”这个代价往往比查找本身还高。你在一个数组里插入一个新元素为了保持有序平均要搬移一半的数据这个开销是O(n)。所以如果你的场景是“少量查找、频繁更新”二分查找不一定比顺序查找好只有在“大量查找、偶尔更新”时它才能发挥威力。第二点哈希表解决90%的查询性能问题但剩下的10%很难缠。哈希表实现简单、性能好但它有一个天然的弱项区间查询。如果你要在哈希表里查“值在100到200之间的所有元素”那只能遍历所有桶性能完全退化。这种场景下有序数组BST索引或者B树反而更合适。选型时必须先问清楚业务要查的是“精确匹配”还是“范围匹配”这两者的数据结构选择是完全不同的。第三点小数据量时别迷恋复杂算法。我在第2章里提过数据量小于几十个元素时顺序查找的效率往往超过二分查找。这不只是缓存问题还涉及到代码分支预测、函数调用开销等多个因素。工程上最好的做法是写一个“混合策略”数据量小用顺序查找数据量大用更高效的算法。这种思路在标准库里很常见比如glibc的qsort会根据区间大小切换排序算法。第四点可读性也是一种性能指标。我曾经接手过一段代码作者为了追求极致性能用位运算、宏定义、算法优化写了一堆难以理解的查找逻辑。结果后期加需求改Bug时团队花在理解这段代码上的时间远超那点性能提升带来的收益。尤其是在嵌入式团队代码是持续维护的资产不是一次性的参赛作品。“一眼能看懂你在干什么”的方案往往才是最适合工程落地的方案。好的查找算法实现应该是数据组织方式清晰、边界条件明确、接口简单而不是把各种技巧堆叠在一起。最后想说的是查找算法本身不难难点在于把算法和你实际的数据场景、硬件环境、生命周期管理结合起来做选型。这篇文章里对比的几种算法每种都有它不可替代的适用场景。抛开场景谈算法优劣没有意义真正的高手是能在一堆约束条件下选出“最不坏”的方案的人。希望这篇文章能帮你在下次写查找代码时多一些底气和判断依据。
