此页面需较新浏览器(支持 SharedArrayBuffer)。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
两种查找方法
- 查找就是找出某个值在数组里的位置(或者说它不在)。
- 线性查找一个一个地检查每个元素。它对任何数组都有效。
- 二分查找快得多,但需要数组先排好序。
线性查找
- 从下标
0走到n - 1,把每个元素和目标比较。 - 一找到就立刻返回它的下标。如果走到末尾,返回
-1。 - 对于有
n个元素的数组,这最多查看n个。
为什么排序能用二分查找
- 如果数组排好序了,你可以直接跳到中间来比较。
- 如果中间的值太小,目标一定在右半边;如果太大,就在左半边。
- 每一步都丢掉一半的数组,所以非常快(大约
log2(n)步)。
low、high、mid
- 保留两个边界:
low(起点)和high(终点)。中点是mid = low + (high - low) / 2。 - 如果
a[mid]是目标,返回mid。如果a[mid] < target,把low = mid + 1;否则high = mid - 1。 - 当
low > high时停止 —— 目标不在里面,返回-1。
English
#include <stdio.h>
int main(void) {
int a[] = {1, 3, 5, 7, 9}; // sorted!
int target = 7, lo = 0, hi = 4, found = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) { found = mid; break; }
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
printf("%d\n", found); // 3
return 0;
}
常见错误
- 二分查找需要已排序的数组。
- 线性查找逐个检查元素。
现在轮到你
- 二分查找时,假设数组已经排好序。用
low、high和mid。 - 找不到时返回
-1。不要自己写main—— 检查器会提供。
探索
线性 vs 二分查找
二分查找每步把范围减半。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
完成 int linear_search(const int a[], int n, int target),让它返回第一个 target 的下标;如果不在数组里则返回 -1。不要写 main。
点击“运行”查看此处输出。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
为一个已排序的数组完成 int binary_search(const int a[], int n, int target)。返回 target 的下标,或 -1。使用 low、high 和 mid。不要写 main。
点击“运行”查看此处输出。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
完成 int first_negative(const int a[], int n),让它返回第一个小于 0 的元素的下标;如果没有则返回 -1。不要写 main。
点击“运行”查看此处输出。