Searching: linear and binary · 查找:线性与二分
Two ways to search
- Searching means finding where a value is in an array (or saying it is not there).
- Linear search checks every item one by one. It works on any array.
- Binary search is much faster but needs the array to be sorted first.
两种查找方法
- 查找就是找出某个值在数组里的位置(或者说它不在)。
- 线性查找一个一个地检查每个元素。它对任何数组都有效。
- 二分查找快得多,但需要数组先排好序。
Linear search
- Walk from index
0ton - 1, comparing each item to the target. - Return the index the moment you find it. If you reach the end, return
-1. - For an array of
nitems, this looks at up tonof them.
线性查找
- 从下标
0走到n - 1,把每个元素和目标比较。 - 一找到就立刻返回它的下标。如果走到末尾,返回
-1。 - 对于有
n个元素的数组,这最多查看n个。
Why sorting enables binary search
- If the array is sorted, you can jump to the middle and compare.
- If the middle is too small, the target must be in the right half; if too big, the left half.
- Each step throws away half the array, so it is very fast (about
log2(n)steps).
为什么排序能用二分查找
- 如果数组排好序了,你可以直接跳到中间来比较。
- 如果中间的值太小,目标一定在右半边;如果太大,就在左半边。
- 每一步都丢掉一半的数组,所以非常快(大约
log2(n)步)。
low, high, mid
- Keep two bounds:
low(start) andhigh(end). The middle ismid = low + (high - low) / 2. - If
a[mid]is the target, returnmid. Ifa[mid] < target, movelow = mid + 1; elsehigh = mid - 1. - Stop when
low > high— the target is not there, so return-1.
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。
#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;
}
Common mistakes
- Binary search needs a sorted array.
- Linear search checks each element in turn.
常见错误
- 二分查找需要已排序的数组。
- 线性查找逐个检查元素。
Now you try
- For binary search, assume the array is already sorted. Use
low,high, andmid. - Return
-1when the value is not found. Do not write amain— the checker provides one.
现在轮到你了
- 二分查找时,假设数组已经排好序。用
low、high和mid。 - 找不到时返回
-1。不要自己写main—— 检查器会提供。
Linear vs binary search · 线性 vs 二分查找
Binary search halves the range each step. · 二分查找每步把范围减半。
Complete int linear_search(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not in the array. Do not · 不 write a main. · 完成 int linear_search(const int a[], int n, int target),让它返回第一个 target 的下标;如果不在数组里则返回 -1。不要写 main。
Click Run to see the output here. · 点击“运行”查看此处输出。
Complete int binary_search(const int a[], int n, int target) for a sorted array. Return the index of target, or -1. Use low, high, and mid. Do not · 不 write a main. · 为一个已排序的数组完成 int binary_search(const int a[], int n, int target)。返回 target 的下标,或 -1。使用 low、high 和 mid。不要写 main。
Click Run to see the output here. · 点击“运行”查看此处输出。
Complete int first_negative(const int a[], int n) so it returns the index of the first item less than 0, or -1 if there is none. Do not · 不 write a main. · 完成 int first_negative(const int a[], int n),让它返回第一个小于 0 的元素的下标;如果没有则返回 -1。不要写 main。
Click Run to see the output here. · 点击“运行”查看此处输出。