搜索：线性搜索与二分搜索

初中计算机科学对已排序的唯一偶整数数组进行精确查找，索引从零开始

使用通行证解锁此实验

通行证可解锁网站上的所有模拟，包括课堂演示模式。下方的教学笔记仍向所有人免费开放。

查看通行证我已经有通行证

一次性付款，无需订阅。

关于此实验

并排使用线性搜索和二分搜索查找同一个目标。每一步中，每种尚未结束的算法各进行一次比较。二分搜索检查剩余有序区间的中间位置；线性搜索则每次向前移动一个位置。选择一个奇数作为目标，可以看到两种算法都在未找到匹配项的情况下结束。

学习目标

跟踪二分搜索中的候选区间和中间位置
比较线性搜索和二分搜索的比较次数
说明二分搜索为何需要有序数据，以及如何处理不存在的目标

使用方法

1在默认数组中搜索32，每次进行一次比较。
2注意二分搜索何时结束，然后继续执行，直到线性搜索结束。
3选择一个奇数目标，例如31。观察二分搜索如何得到空区间。
4更改数组长度并搜索最后一个值。比较最坏情况下的上界。

模型

m = ⌊ \frac{ℓ + h}{2} ⌋

二分搜索中包含低位和高位索引的中间位置

C_{binary, max} = ⌊ lo g_{2} n ⌋ + 1 (n \geq 1)

二分搜索值比较次数的上界

C_{linear, max} = n

此处所示线性搜索在最坏情况下的比较次数

假设

数组包含按升序排列且互不重复的偶数整数 2、4、…、2n。索引从 0 开始。
一次值比较是与目标值进行的一次三向比较。索引运算和循环条件检查不计入比较次数。
如果目标值不存在，线性搜索会扫描整个数组，不会利用数组已排序这一点进行提前停止优化。
一行保持在其搜索已完成的状态，同时另一种搜索继续进行。当前候选区间会在应用当前探测结果之前显示。

在课堂上试试这个实验

Q1为什么二分搜索只需比较一次，就可以排除剩余位置的一半？
Q2在一个包含 32 个值的数组中，用每种方法查找最后一个值分别需要进行多少次比较？
Q3如果将相同的中点规则应用于未排序的数组，会出什么问题？

常见问题

为什么二分搜索无法找到奇数目标值？

数组中的每个元素都是偶数。奇数目标值不可能匹配，因此候选区间最终会变空，算法会报告未找到。

为什么其中一行不再移动了？

该搜索已完成。继续逐步执行会让另一种算法继续运行，以便比较两者的总比较成本。