線形探索法と2分探索法、前提条件と計算量をどう見分けるか
ITパスポート試験 令和5年度 問69 ／ アルゴリズムとプログラミング › アルゴリズムとプログラミング
過去問にチャレンジ
配列に格納されているデータを探索するときの，探索アルゴリズムに関する記述のうち，適切なものはどれか。
- ア
2分探索法は，探索対象となる配列の先頭の要素から順に探索する。
- イ
線形探索法で探索するのに必要な計算量は，探索対象となる配列の要素数に比例する。
- ウ
線形探索法を用いるためには，探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
- エ
探索対象となる配列が同一であれば，探索に必要な計算量は探索する値によらず，2分探索法が線形探索法よりも少ない。
会話形式の解説
講師この問題は、配列からデータを探す2つの方法、線形探索法と2分探索法の説明のうち、適切なものを選ぶ問題です。探し方、データを並べ替えておく必要があるか、計算量の3点に注目してください。
受験者名前が似ているので、どちらが先頭から順に探す方法なのか、いつも混ざってしまいます。
講師線形探索法は、先頭から1つずつ順に比べていく方法です。2分探索法は、並べ替え済みのデータの中央の要素と比べて、探す範囲を半分に絞る操作を繰り返します。「線」のようにまっすぐ進むのが線形、「2つに分ける」のが2分と覚えると区別しやすいです。
受験者そうすると、2分探索法を「先頭の要素から順に探索する」と説明している選択肢は、線形探索法の説明と入れ替わっているのですね。
講師そのとおりです。では、線形探索法を使うにはデータを昇順か降順にソート、つまり並べ替えておく必要がある、という選択肢はどうでしょう。
受験者先頭から順に比べるだけなら、並び順は関係なさそうです。ソートが必要なのは、中央と比べて大小で範囲を絞る2分探索法のほうだと思います。
講師正しいです。線形探索法は先頭から順に1つずつ比べていくので、並び順に関係なく使えます。2分探索法は、中央の値より大きいか小さいかで残す半分を決めるため、整列済みであることが前提です。
受験者計算量が要素数に比例するという選択肢は、線形探索法なら要素が増えるほど比べる回数も増えるので、合っている気がします。
講師はい、それが正解です。計算量は処理にかかる手間の目安のことです。要素数をnとすると、線形探索法の比較回数は最悪でn回、平均でおよそn/2回です。要素数が2倍になれば比較回数もおよそ2倍になるので、計算量はO(n)と表します。
受験者残りの、同じ配列なら探す値によらず2分探索法のほうが計算量が少ない、という選択肢で迷いました。2分探索法のほうが速いと習ったので、正しいように見えます。
講師一般には2分探索法のほうが効率がよいです。ただ、探す値が配列の先頭にある場合を考えてみてください。
受験者線形探索法なら1回比べただけで見つかりますね。それなら2分探索法より少なく済むので、「値によらず」とはいえないということですか。
講師そうです。比較回数は探す値の位置によって変わるので、「常に」少ないとは言い切れません。「値によらず」「常に」のような例外を認めない言い方を見たら、反例がないかを考えるのがコツです。
受験者整理すると、線形探索法は先頭から順に探し、ソート不要で計算量は要素数に比例する。2分探索法は中央と比べて範囲を半分にし、ソートが前提。ただし、いつでも2分探索法が少ないとは限らない、ですね。
講師よくまとまっています。補足すると、2分探索法の計算量はO(log n)と表され、要素数が増えても比較回数はゆるやかにしか増えません。また、キーから格納位置を直接計算して探すハッシュ法も、関連する探索方法として押さえておくとよいでしょう。
まとめ
線形探索法は配列の先頭から1つずつ順に比べる方法で、データが並べ替えられていなくても使え、計算量は要素数に比例します（O(n)）。2分探索法は整列済みのデータの中央の要素と比べて探す範囲を半分ずつ絞る方法で、昇順または降順のソートが前提です。2分探索法は一般に効率がよいものの、探す値が先頭にある場合などは線形探索法のほうが比較回数が少なくなるため、「値によらず常に少ない」とはいえません。2つの方法の特徴を入れ替えた選択肢や、例外を認めない言い切り表現に注意しましょう。
解答・解説
正解はイです
この問題のテーマ
配列の中からデータを探す2つの方法、線形探索法と2分探索法について、探し方の違い、使える条件、比較する回数の増え方を選ぶ問題です。
解き方の考え方
最初に、2つの探索法の基本的な動きを整理します。線形探索法は先頭から1つずつ順に比べていく方法で、データが並べ替えられていなくても使えます。2分探索法は、整列済みのデータの中央の要素と比べて探す範囲を半分に絞る操作を繰り返す方法です。この違いを頭に置いたうえで、各選択肢の説明が「どちらの方法の特徴か」と「いつでも成り立つか」の2点を確かめると、正解を選べます。
選択肢ごとの解説
- ×ア 2分探索法は，探索対象となる配列の先頭の要素から順に探索する。2分探索法を「先頭の要素から順に探索する」と述べた肢です。先頭から順に探すのは線形探索法の進め方です。2分探索法は、中央の要素と比べて探す範囲を半分ずつ絞ります。2つの方法の説明が入れ替わっているので、誤りです。
- ○イ 線形探索法で探索するのに必要な計算量は，探索対象となる配列の要素数に比例する。線形探索法の計算量は、要素数に比例するという肢です。要素数をnとすると、比較回数は最悪でn回、平均でおよそn/2回です。要素数が2倍になれば比較回数もおよそ2倍になるので、計算量はO(n)と表されます。したがって、正しい説明です。
- ×ウ 線形探索法を用いるためには，探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。線形探索法を使うには、ソート済みであることが必要だという肢です。線形探索法は先頭から順に確かめるので、並び順に関係なく使えます。昇順または降順に整列しておく必要があるのは2分探索法のほうです。したがって、誤りです。
- ×エ 探索対象となる配列が同一であれば，探索に必要な計算量は探索する値によらず，2分探索法が線形探索法よりも少ない。探す値によらず、2分探索法のほうが必ず比較が少ないという肢です。たとえば探す値が配列の先頭にあれば、線形探索法は1回の比較で見つかり、2分探索法より少なく済みます。比較回数は探す値の位置で変わるので、「値によらず」は成り立たず、誤りです。
補足
2つの方法の特徴を入れ替えた選択肢（アやウ）や、「常に」「値によらず」のように例外を認めない言い方の選択肢（エ）には注意が必要です。言い切る表現を見たら、反例がないかを考えると判断しやすくなります。2分探索法の計算量はO(log n)と表され、要素数が増えても比較回数の増え方はゆるやかです。また、キーから格納位置を直接計算して探すハッシュ法も、関連する探索方法として押さえておくとよいでしょう。
POINT
- 線形探索法は先頭から順に比べる方法で、データが整列されていなくても使えます。
- 線形探索法の比較回数は最悪でn回、平均で約n/2回で、計算量は要素数に比例します（O(n)）。
- 2分探索法は中央の要素と比べて探す範囲を半分に絞る方法で、データが昇順または降順に整列済みであることが前提です。
- 2分探索法は一般に効率がよい方法ですが、探す値の位置によっては線形探索法のほうが比較回数が少ない場合もあります。