問69
頻出度★★☆
配列に格納されているデータを探索するときの, 探索アルゴリズムに関する記述のうち, 適切なものはどれか。
令和5年度 ITパスポート試験 問69
This question's explanation and your answers so far.
解説
問 69
Incorrectア
Searching in order from the first element of the array is the behavior of a linear search. Binary search compares with the middle element of a sorted array and narrows the search range by half each time based on whether the target is larger or smaller, so it does not examine elements in order from the first one. This statement mixes up the two algorithms, so it is wrong.
- イ
正解 The correct answer is イ. A linear search compares the target value with each element in order, starting from the first element of the array, and in the worst case it examines every element up to the last one. If the number of elements is n, the number of comparisons is at most n, and on average it is also proportional to n, so the amount of computation is O(n) in order notation; that is, it is proportional to the number of elements in the array. Therefore “the amount of computation required for a linear search is proportional to the number of elements in the target array” is an appropriate statement.
Incorrectウ
The one that requires the elements to be sorted in ascending or descending order is binary search. A linear search simply checks every element in order from the first one, so it can be used as-is even on an unsorted array. This statement reverses the requirement, so it is wrong.
Incorrectエ
It is not the case that binary search always requires less computation “regardless of the value being searched for.” For example, when the target value is near the front of the array, a linear search can find it in one or a few comparisons, whereas binary search narrows down from the middle and does not necessarily finish with fewer comparisons. Which one is better changes depending on the value being searched for and its position, so it is wrong.
ここがポイント
- A linear search is a simple method that compares elements in order from the first one; its computational cost is O(n) (proportional to the number of elements). No prior sorting is needed.
- Binary search assumes a sorted array and narrows the search range by half each time by comparing with the middle element, so it is fast at O(log n); however, in cases such as when the target value is near the front, a linear search can sometimes be more advantageous.
用語