問69
頻出度★★☆
配列に格納されているデータを探索するときの, 探索アルゴリズムに関する記述のうち, 適切なものはどれか。
令和5年度 ITパスポート試験 問69
这道题的解析和你的作答记录。
解説
問 69
错误ア
从数组的首个元素开始依次查找是线性查找法的行为。二分查找法是与已排序数组的中间元素进行比较，根据大小关系将查找范围每次缩小一半的方式，因此不会从首个元素开始依次检查。这是把两种算法弄混了，所以错误。
- イ
正解 正确答案是イ。线性查找法是从数组的首个元素开始，逐个元素依次与目标值进行比较的方式，最坏情况下要检查到末尾的全部元素。设元素个数为 n，则比较次数最多为 n 次，平均也与 n 成正比，因此计算量用阶（order）来表示为 O(n)，即与数组的元素个数成正比。所以「线性查找法进行查找所需的计算量与查找对象数组的元素个数成正比」是恰当的描述。
错误ウ
元素必须按升序或降序排序的是二分查找法。线性查找法只是从首个元素开始依次确认全部元素，所以即使是未排序的数组也能直接使用。这里把要求弄反了，所以错误。
错误エ
并非「无论查找哪个值」二分查找法的计算量都一定更少。例如当目标值位于数组首部附近时，线性查找法只需 1 次或几次比较就能找到，而二分查找法是从中间开始缩小范围，未必能用更少的比较完成。优劣会随查找的值及其位置而变化，所以错误。
ここがポイント
- 线性查找法是从首个元素开始依次比较的简单方式，计算量为 O(n)（与元素个数成正比）。无需事先排序。
- 二分查找法以已排序数组为前提，通过与中间元素比较将查找范围每次缩小一半，因此计算量为 O(log n)，速度更快；但在目标值位于首部附近等情况下，线性查找有时反而更有利。
用語