C语言在线编程环境：https://sky315.com:8080/c/。
C语言课上你主要会碰到两种查找方法：顺序查找和二分查找。这两种方法的差距有多大呢？打个比方，顺序查找像是你在图书馆里一本一本地翻，二分查找像是你直接翻到中间，根据字母顺序决定往前翻还是往后翻。数据少的时候感觉不出来，数据多了，那差距简直是自行车和跑车的区别。
例1：顺序查找——最朴素的挨个看
顺序查找的思路简单到不用动脑子：从第一个开始，挨个往后看，找到目标就停，找完了都没找到就说明不存在。
场景：给你一个数组，让你找某个数在不在里面，如果在的话在第几个位置。
#include <stdio.h> int main() { int a[10] = {3, 7, 1, 9, 4, 6, 8, 2, 5, 0}; int target, i; int index = -1; // -1表示没找到 printf("请输入要查找的数："); scanf("%d", &target); for (i = 0; i < 10; i++) { if (a[i] == target) { index = i; break; // 找到了，不找了 } } if (index != -1) { printf("找到了，在第%d个位置（下标%d）\n", index + 1, index); } else { printf("没找到\n"); } return 0; }
拆开看：
-
int index = -1;又是标志变量的套路。先设成-1代表"没找到"，找到了就改成实际下标。 -
for (i = 0; i < 10; i++)从头到尾遍历数组。 -
if (a[i] == target)找到了目标，把下标记下来，break跳出循环——既然已经找到了，后面的元素就不用再看了，省时间。 -
循环结束后判断
index是不是-1，决定输出什么结果。
这个算法有什么问题？
效率。如果数组里有100万个元素，你要找的数正好在最后一位，那就得比100万次。如果这个数根本不存在，那就得把100万个全比一遍，才能确定"没有"。这是最坏情况。
平均情况下，顺序查找需要比较n/2次。也就是说100万个数据，平均要找50万次。这个效率你能接受吗？看场景。如果数据量小（几十个几百个），顺序查找完全够用。如果数据量大，就得换方法。
一个小优化：设置"哨兵"
如果你经常要在数组里查找，有个小技巧可以让你少写一条判断。把目标值放在数组末尾作为"哨兵"，这样就不用每次判断是否越界了，反正最后一定能找到（找到哨兵了就说明原数组里没有）。
int a[11] = {3, 7, 1, 9, 4, 6, 8, 2, 5, 0, 0}; int target; int i = 0; scanf("%d", &target); a[10] = target; // 把目标放在末尾当哨兵 while (a[i] != target) { i++; } if (i == 10) { printf("没找到\n"); } else { printf("找到了，下标%d\n", i); }
这个写法在数据量特别大的时候能省一点时间，但代码可读性其实不如前一种。平时写代码，可读性比那一点点性能重要，所以知道有这回事就行，不用刻意用。
顺序查找就说到这儿。它最大的优点是不需要数据有序，拿来就能查。缺点也明显，就是慢。
例2：二分查找——砍半查找，效率翻倍
二分查找的前提条件：数组必须是有序的（从小到大或者从大到小）。这是它的门槛，也是它的优势。
思路特别像小时候玩的"猜数字"游戏：让你猜1到100之间的一个数，你猜50，告诉你大了还是小了，然后你猜25或者75，不断缩小范围，直到猜中。每次排除一半的可能性，这就是二分查找的精髓。
假如数组是{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}，要找13。过程是这样的：
-
先看最中间的数（第5个位置，值是11）。13比11大，说明要往右半边找。
-
右半边是
{13, 15, 17, 19}，中间是15，13比15小，往左半边找。 -
左半边是
{13}，找到了。
代码怎么写？
#include <stdio.h> int main() { int a[10] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; int target; int left = 0, right = 9, mid; int index = -1; printf("请输入要查找的数："); scanf("%d", &target); while (left <= right) { mid = (left + right) / 2; // 取中间位置 if (a[mid] == target) { index = mid; break; } else if (a[mid] < target) { left = mid + 1; // 目标在右半边 } else { right = mid - 1; // 目标在左半边 } } if (index != -1) { printf("找到了，下标%d\n", index); } else { printf("没找到\n"); } return 0; }
拆开看，每一步都重要：
-
left = 0, right = 9初始化查找范围的左右边界。一开始是整个数组，左边界在第0位，右边界在第9位。 -
while (left <= right)循环条件是左边界不超过右边界。如果left > right了，说明范围已经缩没了，找不到了。 -
mid = (left + right) / 2;取中间位置。注意这里整数除法自动截断，比如(0+9)/2=4，取的是中间偏左的那个。 -
三种情况判断：
-
a[mid] == target：中了，记下下标，break出去。 -
a[mid] < target：中间值比目标小，说明目标在右半边，把左边界移到mid + 1。为啥是加1？因为mid本身已经不可能是目标了，直接跳过它。 -
a[mid] > target：中间值比目标大，说明目标在左半边，把右边界移到mid - 1。同理，mid可以排除了。
-
追踪一次执行过程，看变量怎么变的：
数组是{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}，找13。
初始：left=0，right=9，mid=(0+9)/2=4，a[4]=9。9<13，所以left=5。
第二轮：left=5，right=9，mid=(5+9)/2=7，a[7]=15。15>13，所以right=6。
第三轮：left=5，right=6，mid=(5+6)/2=5，a[5]=11。11<13，所以left=6。
第四轮：left=6，right=6，mid=(6+6)/2=6，a[6]=13。找到了。
总共只比了4次。如果这10个数用顺序查找，平均要5次，最坏10次。差距不大？那换大一点的数据：100万个有序数，二分查找最多只要20次（因为2的20次方约等于100万），而顺序查找平均50万次。这才叫天壤之别。
二分查找的变种：递归写法
如果你学了递归，二分查找可以写得更简洁：
int binary_search(int a[], int left, int right, int target) { if (left > right) { return -1; // 没找到 } int mid = (left + right) / 2; if (a[mid] == target) { return mid; } else if (a[mid] < target) { return binary_search(a, mid + 1, right, target); } else { return binary_search(a, left, mid - 1, target); } }
递归写法更接近"分治"的数学描述，但循环写法在效率上更好（没有函数调用的开销）。笔试的时候两种都能写，循环写法更保险，不容易栈溢出。
例3：找最接近的值——二分查找的变种
有时候你不仅要找"等于目标"的数，还可能要找"最接近目标"的数。比如成绩系统里，给定一个分数，要找最接近它的人。
思路还是二分查找，但即使找不到精确匹配，也要返回当前区间里离目标最近的那个。
#include <stdio.h> #include <stdlib.h> // 用了abs函数 int main() { int a[10] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; int target; int left = 0, right = 9, mid; int closest = a[0]; printf("请输入目标值："); scanf("%d", &target); while (left <= right) { mid = (left + right) / 2; // 更新最接近的值 if (abs(a[mid] - target) < abs(closest - target)) { closest = a[mid]; } if (a[mid] == target) { closest = a[mid]; break; } else if (a[mid] < target) { left = mid + 1; } else { right = mid - 1; } } printf("最接近%d的数是%d\n", target, closest); return 0; }
这个例子的重点是：二分查找的框架可以修改来适应不同的需求。 不一定非要"找到就停"，你也可以在查找过程中记录中间结果，等循环结束之后返回那个最合适的。
例4：在有序数组中插入一个数——查找加挪动
这个题把查找和数组操作结合起来了。给定一个有序数组，插入一个新数，保持有序。
思路分两步：先用二分查找（或者顺序查找）找到该插在哪儿，然后把那个位置之后的元素全部往后挪一位，把新数放进去。
#include <stdio.h> int main() { int a[11] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; int n = 10; // 当前有10个元素 int target; int pos, i; printf("请输入要插入的数："); scanf("%d", &target); // 第一步：找插入位置（用顺序查找，因为数组规模小） pos = 0; while (pos < n && a[pos] < target) { pos++; } // 第二步：从后往前挪，腾出位置 for (i = n; i > pos; i--) { a[i] = a[i - 1]; } a[pos] = target; n++; // 元素个数加1 // 输出插入后的数组 for (i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); return 0; }
这里的关键是挪动方向必须从后往前。如果你从前往后挪，前面的值会覆盖后面的值，数据全乱套了。你可以自己在脑子里模拟一下：数组是{1,3,5,7,9}，要在位置2插入4。从后往前挪：先把9挪到下标5，再把7挪到下标4，再把5挪到下标3，然后在下标2放4。完美。如果从前往后挪：先把1挪到下标1？那3就被覆盖了，全完了。
如果这个数组特别大，找位置可以用二分查找来优化，挪动这步没法省（除非你换链表）。这个题就是你前面学的"顺序查找"在实际场景里的应用。
两种查找方式的对比，一张表说清楚：
| 顺序查找 | 二分查找 | |
|---|---|---|
| 前提条件 | 无 | 数组必须有序 |
| 平均时间复杂度 | O(n) | O(log n) |
| 最坏情况 | O(n) | O(log n) |
| 实现难度 | 简单 | 稍复杂（主要是边界条件） |
| 适用场景 | 数据量小、数据无序 | 数据量大且有序、查找频繁 |
什么叫O(n)和O(log n)？ 通俗点说：O(n)就是数据量翻倍，查找时间也翻倍；O(log n)就是数据量翻倍，查找时间只增加一点点（因为是对数增长）。100万个数，顺序查找最坏要100万次，二分查找只要20次。这个差距是指数级别的，数据越大越明显。
几个必踩的坑：
坑1：二分查找的边界条件写错
while (left < right)还是while (left <= right)？这俩差着一个等于号，效果完全不同。我建议你用<=，配合left = mid + 1和right = mid - 1，这样逻辑清晰，不容易死循环。
如果你用<，那你就得保证退出的时候left和right已经相遇了，处理起来更绕。新手统一用<=，稳妥。
坑2：mid的计算溢出
mid = (left + right) / 2;在left和right很大的时候（比如接近int最大值），left+right可能会溢出。更安全的写法是mid = left + (right - left) / 2;。平时写作业数据量小，看不出问题，但大项目里这是隐患。养成习惯写后面这种。
坑3：二分查找前提是数组有序
你拿个乱序数组去跑二分查找，结果完全是随机的。排序的算法咱们下一篇详细讲，但你心里得有这根弦——二分查找之前，先排序。
坑4：顺序查找的break别忘了
有些人写了if (a[i] == target)之后忘了break，循环继续跑，最后返回的是最后一个匹配的位置，而不是第一个。如果数组里有重复元素，这个差别就很要命了。
最后说两句：
查找算法看着简单，但它背后反映的是一个核心思想：能不能用数据的某种结构（比如有序性）来加速查找过程？ 这个思想扩展到后面，就是哈希表、二叉搜索树、B树这些数据结构的基础。你现在学的二分查找，就是这条路上的第一步。
练到什么程度算过关？ 顺序查找随手就写出来，二分查找的循环边界条件和更新逻辑不犹豫，知道什么时候该用哪种查找。把上面几个例子自己敲一遍，改改数据跑一跑，尤其是把二分查找的边界条件写错几次看看会出现什么结果——出一次错你就能记住一辈子。