数据结构与算法 / 系统课时
顺序查找
顺序查找
顺序查找按原数组顺序逐个检查元素,不要求排序。本课同时返回第一次出现的位置和元素比较次数。这个例子与第 3 章按概率计算查找成本的模型对应,也能用于验证二分查找的边界。
学习目标
- 区分首次命中、未命中、空数组和非法引用。
- 用前缀状态说明为什么返回的是首次出现位置。
- 推导实际比较次数,并判断预处理是否值得。
输入、输出与检查顺序
接收一个非空引用的 int[] 和目标整数,数组本身可为空。返回首次匹配的 0 起始下标;未找到时返回 -1。函数只读取数组。这里“比较次数”只算 values[index] == target,不计循环条件、返回和打印。
在检查位置 index 之前,区间 [0,index) 中都没有目标。当前位置相等就直接返回,因此不可能漏掉更早匹配。若不等,下一轮的前缀多排除一个位置。不命中时整个数组最终都被排除。Java 下标必须小于数组长度,空数组不会执行任何元素比较。 Java 数组访问规定
Java 17 实例
保存为 SequentialSearchDemo.java。执行 javac -encoding UTF-8 --release 17 SequentialSearchDemo.java,再执行 java SequentialSearchDemo。
import java.util.Arrays;
import java.util.Objects;
public class SequentialSearchDemo {
public record SearchResult(int index, int comparisons) {
public boolean found() {
return index >= 0;
}
}
public static SearchResult sequentialSearch(int[] values, int target) {
Objects.requireNonNull(values, "values");
for (int index = 0; index < values.length; index++) {
if (values[index] == target) {
return new SearchResult(index, index + 1);
}
}
return new SearchResult(-1, values.length);
}
private static void printResult(int[] values, int target) {
SearchResult result = sequentialSearch(values, target);
System.out.printf("数组=%s, 目标=%d, 下标=%d, 比较次数=%d%n",
Arrays.toString(values), target, result.index(), result.comparisons());
}
public static void main(String[] args) {
int[] values = {18, 7, 25, 7, 42};
printResult(values, 18);
printResult(values, 7);
printResult(values, 99);
printResult(new int[0], 7);
}
}数组=[18, 7, 25, 7, 42], 目标=18, 下标=0, 比较次数=1
数组=[18, 7, 25, 7, 42], 目标=7, 下标=1, 比较次数=2
数组=[18, 7, 25, 7, 42], 目标=99, 下标=-1, 比较次数=5
数组=[], 目标=7, 下标=-1, 比较次数=0成本和使用边界
第一次命中位于 i 时比较 i+1 次;未命中比较 n 次。对长度大于 0 的数组,最好为 ,最坏为 ,只使用固定数量的辅助变量。平均情况要说明查询分布,例如互异元素中均匀命中时是 ,有重复值时仍按首次出现的位置计。演示打印整个数组的成本不属于查找函数。
同一静态数据查询多次时,可比较排序或建索引的成本、后续查询频率和更新代价。排序副本后返回的是排序后的位置。若任务需要原数组的首次下标,应在索引中保留原位置或用其他契约。 Java Arrays 二分查找前提
本课练习
改为返回最后一次出现的下标,核对目标 7 应返回 3,并说明从右向左扫描时如何计算比较次数。下一课利用非递减顺序缩小待查范围。