2分探索が使えるデータ構造はどんな並び方か
基本情報技術者試験 平成29年度春期 午前 問7 ／ アルゴリズムとプログラミング › アルゴリズム
過去問にチャレンジ
顧客番号をキーとして顧客データを検索する場合，2分探索を使用するのが適しているものはどれか。
- ア
顧客番号から求めたハッシュ値が指し示す位置に配置されているデータ構造
- イ
顧客番号に関係なく，ランダムに配置されているデータ構造
- ウ
顧客番号の昇順に配置されているデータ構造
- エ
顧客番号をセルに格納し，セルのアドレス順に配置されているデータ構造
会話形式の解説
講師この問題は、2分探索を使うにはデータがどう並んでいる必要があるかを問うものです。選択肢ごとに、顧客番号の大小の順に並んでいるかどうかに注目してください。
受験者2分探索は、真ん中を見て半分ずつ絞っていく方法でしたよね。並び方がそんなに関係するのですか。
講師大いに関係します。中央の値と探したい値を比べたあと、目的の値が中央より前にあるか後ろにあるかを決めて、範囲を半分にします。その判断ができる条件は何だと思いますか。
受験者中央より小さい番号は前、大きい番号は後ろにある、と言い切れる必要があります。つまり、顧客番号の順に整列していることが条件ですね。
講師そのとおりです。昇順か降順に整列していれば、目的の番号が中央より小さいときは前半、大きいときは後半に絞り込めます。そうすると、顧客番号の昇順に配置したデータ構造は条件を満たします。
受験者ハッシュ値で置き場所を決める構造も、顧客番号から計算しているので、ある程度は番号順に並ぶのではないかと思いました。
講師そこが引っかかりやすいところです。置き場所はハッシュ関数（キーから格納位置を計算する関数）の結果で決まるので、顧客番号の大小の順に並ぶとは限りません。この構造には、ハッシュ値から位置を直接求める探索法を使います。
受験者なるほど。番号から計算していても、大小の順が保たれるわけではないのですね。ランダムに並べた構造は、中央と比べても前後どちらにあるか決められないので使えません。
講師はい。もう一つ、顧客番号をセルに格納してセルのアドレス順に並べた構造はどうでしょうか。
受験者「順に配置」とあるので、整列しているようにも見えます。でも、アドレス順というのは何の順なのでしょうか。
講師アドレスは記憶上の位置を表す番号です。セルのアドレス順は顧客番号の大小とは関係なく決まるので、顧客番号の昇順になるとは限りません。アドレス順と顧客番号順は別の基準だと考えてください。
受験者「順」という言葉があっても、何の順なのかを確かめる必要があるのですね。キーである顧客番号の順に並んでいるのは昇順の構造だけなので、それが正解だと分かりました。
講師よく整理できています。補足すると、2分探索は中央の要素を直接取り出すので、添字で任意の位置を参照できる配列のような構造が向いています。また、挿入や削除が多いデータでは整列した状態を保つ手間がかかる点も覚えておくとよいです。
まとめ
2分探索は、探索範囲の中央の値と探したい値を比べ、前半か後半かに範囲を半分ずつ絞り込む探索法です。この絞り込みができるのは、データがキーの昇順か降順に整列している場合だけです。ハッシュ値で配置した構造は置き場所が計算結果で決まり、キーの大小順になるとは限らないため、ハッシュ値から位置を直接求める探索法を使います。ランダムな配置やセルのアドレス順の配置も顧客番号の順が保証されないので、2分探索には適しません。したがって、顧客番号の昇順に配置したデータ構造が適しています。
解答・解説
正解はウです
この問題のテーマ
2分探索を使うには、データがどのように並んでいる必要があるかを問う問題です。
解き方の考え方
2分探索では、探索範囲の中央にある値と探したい値を比べます。そのうえで「目的の値は中央より前にあるか、後ろにあるか」を判断し、範囲を半分に絞る操作を繰り返します。この判断ができるのは、データがキーの大きい順か小さい順に整列している場合だけです。そこで、各選択肢の並び方が顧客番号の順になっているかを確かめます。
選択肢ごとの解説
- ×ア 顧客番号から求めたハッシュ値が指し示す位置に配置されているデータ構造ハッシュ値が指す位置にデータを置く構造は、ハッシュ関数の計算結果で置き場所が決まります。そのため、顧客番号の大小の順に並ぶとは限りません。この構造に合うのはハッシュ値から直接位置を求める探索法で、2分探索の前提である整列は満たしていません。
- ×イ 顧客番号に関係なく，ランダムに配置されているデータ構造顧客番号と関係なくランダムに並べたデータ構造では、中央の値と比べても、目的のデータが前後どちらにあるかを決められません。範囲を半分に絞れないので、2分探索は使えません。
- ○ウ 顧客番号の昇順に配置されているデータ構造顧客番号の昇順に並べたデータ構造なら、中央の値より目的の番号が小さいときは前半、大きいときは後半に絞り込めます。2分探索の前提である「キーが整列していること」を満たすため、これが適しています。
- ×エ 顧客番号をセルに格納し，セルのアドレス順に配置されているデータ構造セルのアドレス順に並べたデータ構造は、記憶上の物理的な位置の順に並んでいるだけです。顧客番号の大小の順になるとは限りません。キーの順序が保証されないので、中央の値と比べても探索範囲を絞り込めません。
補足
2分探索では中央の要素を直接取り出すので、添字で任意の位置を参照できる配列のような構造が向いています。また、データの挿入や削除が多い場合は、整列した状態を保つ手間がかかる点にも注意が必要です。
POINT
- 2分探索は、キーが昇順か降順に整列したデータにだけ使えます。
- 中央の値との比較で探索範囲を半分ずつ減らすため、データ件数が増えても比較回数はゆっくりとしか増えません。
- ハッシュ値で配置したデータに対しては、2分探索ではなく、ハッシュ値から位置を直接求める探索法を使います。
- 「アドレス順」や「格納順」は物理的な並びのことで、キーの順序とは別のものです。