数据结构与算法 / 系统课时

顺序查找

顺序查找

顺序查找按原数组顺序逐个检查元素,不要求排序。本课同时返回第一次出现的位置和元素比较次数。这个例子与第 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。

java
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);
    }
}
text
数组=[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 的数组,最好为 Θ(1)\Theta(1),最坏为 Θ(n)\Theta(n),只使用固定数量的辅助变量。平均情况要说明查询分布,例如互异元素中均匀命中时是 (n+1)/2(n+1)/2,有重复值时仍按首次出现的位置计。演示打印整个数组的成本不属于查找函数。

同一静态数据查询多次时,可比较排序或建索引的成本、后续查询频率和更新代价。排序副本后返回的是排序后的位置。若任务需要原数组的首次下标,应在索引中保留原位置或用其他契约。 Java Arrays 二分查找前提

本课练习

改为返回最后一次出现的下标,核对目标 7 应返回 3,并说明从右向左扫描时如何计算比较次数。下一课利用非递减顺序缩小待查范围。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

顺序查找

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通