此页面需较新浏览器(支持 SharedArrayBuffer)。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
查找一个值
- 一个常见的工作是查找(search):某个值在不在数组里,以及在哪里?
- 通常的答案是我们找到它的那个下标(index),或者如果不在就返回
-1。 - 我们学习两种方法:线性查找(linear search,适用于任何数组)和二分查找(binary search,需要已排序的数组,但快得多)。
线性查找
- 从下标
0到末尾,逐个查看每个元素。 - 如果这个元素等于目标值,就立刻返回它的下标。
- 如果循环结束都没有匹配,就返回
-1。
English
public class Main {
public static void main(String[] args) {
int[] a = {4, 8, 15, 16, 23};
int target = 15;
int found = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
found = i;
break; // stop early, we have it
}
}
System.out.println(found); // 2
}
}
线性查找有多快?
- 在最坏的情况下(值在最后,或者根本不存在),它会检查每一个元素。
- 对于有
n个元素的列表,这最多是n次检查。我们把这叫作线性(linear)时间。 - 对于小数组这完全没问题。但对于很大的已排序数组,我们可以做得更好。
二分查找需要已排序的数组
- 二分查找只在数组已经排好序(从小到大)时才有效。
- 它检查中间的元素,然后每一步丢掉一半的数组。
- 这快得多:一百万个元素大约只需要 20 次检查,而不是一百万次。
二分查找的思路
- 保留两个边界:
low(开始)和high(结束)。 - 查看中间的下标
mid = (low + high) / 2。 - 如果
a[mid]等于目标值,返回mid。 - 如果
a[mid]太小,目标值一定在右边,所以设low = mid + 1。 - 如果
a[mid]太大,目标值一定在左边,所以设high = mid - 1。 - 当
low超过high时停止;这时值不存在,返回-1。
English
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12, 16, 23, 38}; // sorted!
int target = 16;
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1; // go right
} else {
high = mid - 1; // go left
}
}
System.out.println(found); // 4
}
}
当某个值不存在时
- 当目标值不在数组里时,两种查找都返回
-1。 - 对于二分查找,当
low > high时循环结束 —— 边界交叉了,所以没有地方可以再找了。 - 在调用查找的代码里,一定要处理
-1这种情况。
English
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12}; // sorted
int target = 7; // not in the array
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.println(found); // -1
}
}
常见错误
- 二分查找需要已排序的数组。
- 线性查找是 O(n);二分是 O(log n)。
现在轮到你
- 每个任务都已经填好了类的骨架 —— 把你的代码写在 main 里面,或者补全给出的方法。
- 按 Check answer(检查答案),把你的代码和提供的测试一起编译,并查看结果。保留起始代码里给出的类和方法接口。
- 你的代码在服务器上编译并运行,所以第一次运行也很快。
探索
线性 vs 二分查找
Binary search halves the range each step — far fewer checks.
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
Complete linearSearch(int[] a, int target). Return the 索引 of the first item equal to target, or -1 if it is not in the array. Check items from index 0 upward.
点击“运行”查看此处输出。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
Complete binarySearch(int[] a, int target) for a sorted array. Use low/high bounds and check the middle each step. Return the index of target, or -1 if it is missing.
点击“运行”查看此处输出。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
Complete countOccurrences(int[] a, int target) that returns how many times target appears in a (a linear scan). Return 0 if it never appears.
点击“运行”查看此处输出。