高校情報I 探索アルゴリズム—線形探索と二分探索の比較範囲を表で確かめる｜武蔵野個別指導塾

未整列の配列で候補を捨てる誤りを見つけ、探索の比較回数と未発見になるまでの範囲を表に記録します。

よくあるのは、値がばらばらに並んだ配列の中央を見て、二分探索で残り半分を捨ててしまう場面です。中央の値と目標の大小がわかっても、並び順が保証されていなければ、捨てた側に目標があるかもしれません。探索の問題では、どの値を調べたかと同じくらい、どの範囲を調べずに残したかが重要です。範囲表や授業ノートの表記と照らし、添字や中央の決め方を確認しながら読み進めてください。

問題文から最初に拾う条件

定期テストでは、まず探索の途中経過を表に埋める型が考えられます。配列と目標値が与えられ、比較した位置や値を順番に記録する問題です。答えが見つかった位置だけを書くのではなく、そこに至るまで何回比較したかも問われます。値と位置は別物なので、表にそれぞれの欄を作ると混乱を減らせます。

次に、目標が存在しない場合の終了条件を説明する型があります。最後まで調べる方法と、残りの範囲が空になったときに終了する方法では、未発見と判断する根拠が違います。見つからない場合の出力が指定されていれば、その記号や値を問題文どおりに書きます。配列が空のときも、値との比較をせずに未発見と判断できます。

さらに、2つの方法を同じ配列で比較する型があります。二分探索には並び順の前提が必要です。比較回数は目標の位置や手順によって変わり、どの入力でも一方が少ないと決めつけることはできません。ここでは整列の具体的な手順には立ち入らず、与えられた並びが探索に使えるかを調べます。

探す範囲を保つという考え方

探索は、並んだデータの中から指定された値を探す処理です。線形探索は端から順番に値を比較し、一致したらそこで終了します。最後まで一致しなければ未発見です。並び順は問いませんが、今回の手順では同じ値が複数あるとき、左から最初に見つけた位置を返します。

二分探索は、昇順に並んだ範囲の中央と目標を比較します。中央が目標より小さければ、中央以前は目標より小さいため、右側を次の候補にします。中央が目標より大きければ、左側を候補にします。一致した場合はその場で終了します。同じ値が複数あっても、最初の位置を返すとは限りません。

図1のように、線形探索は次の1要素へ進み、二分探索は中央との大小で候補の範囲を狭めます。候補から外した側に目標がないと説明できることが、二分探索の前提です。未整列の列では大小によるこの説明が成り立ちません。

以下では配列の左端の添字を0とします。右端までの添字を含めた両端を、それぞれ左端と右端と呼びます。中央の添字は両端の添字の和を2で割った整数の商です。たとえば左端が1、右端が4なら中央は2です。小数部分は切り捨てます。候補の要素が偶数個なら中央の2つのうち左側を選ぶことになります。

比較回数は、配列の要素と目標を照合した回数として数えます。範囲が空かどうかを調べる回数は含めません。1回の照合では一致か、小さいか、大きいかを判定します。授業で比較演算子の実行回数を数えるよう指定された場合は、ここでの数え方とは異なるため、その指定を優先します。

基本例題：中央と目標を照らす

自作の整理番号が昇順に並ぶ配列を、左から 4、9、13、18、25、31、37 とします。添字は0から6です。目標の25を二分探索し、比較した値の順番、見つけた添字、比較回数を答えてください。両端を含む範囲と整数の商を使う手順は、先ほどの定義に従います。

1. 最初の候補は添字0から6です。中央は0と6の和を2で割った商で、添字3です。
2. 添字3の値18と25を比較します。18は25より小さいので、添字3以前を候補から外します。
3. 残る範囲は添字4から6です。中央は4と6の和を2で割った商で、添字5です。
4. 添字5の値31と25を比較します。31は25より大きいので、添字5以降を候補から外します。
5. 残る範囲は添字4から4です。中央も添字4で、その値25は目標と一致します。
6. 比較した値は18、31、25の順、見つけた添字は4、比較回数は3回です。

図2のように、候補の両端は比較後に更新します。中央を除くのは、すでに一致しないと確かめたからです。左端や右端を中央のままにすると、候補が1個になった場面で同じ要素を繰り返し調べる恐れがあります。

答えを元の配列に戻すと、添字4には確かに25があります。比較の記録を検算するときは、最初の範囲から一段ずつ再現し、途中の値を飛ばしていないかも確認します。同じ配列で線形探索を使うなら、4、9、13、18、25と比較し、添字4で終了するので5回です。2つの回数の差はこの目標に対する結果です。目標が先頭の4なら、線形探索は1回で終了します。

発展例題：存在しない値を探す

昇順の配列 3、8、14、21、29、40 から、存在しない可能性も含めて目標の20を二分探索します。添字は0から5、中央の決め方と比較回数の定義は基本例題と同じです。一致したら添字、候補がなくなったら「未発見」を答え、比較した値も順番に示してください。

最後は左端3が右端2を越えます。両端を含む範囲に要素は残らないので、値との比較を追加せず「未発見」とします。比較した値は14、29、21で、比較回数は3回です。元の配列を見直すと、20は14と21の間に入る値ですが、その値自体は存在しません。大小の判断で除いた範囲と最後の空の範囲を合わせると、見落としがないことを説明できます。

目標が配列の最小値や最大値のときも同じ規則で追います。端だから最初から除くのではなく、中央と比較した結果、候補として残る側へ進みます。空の配列なら初めから左端0、右端は存在する最後の添字より前の値としてマイナス1と置けます。左端が右端を越えているので、中央の値を読まずに未発見です。

同じ値が複数ある配列では、中央で一致した位置をそのまま返します。最初の一致位置を必ず求める問題なら、追加の規則が必要です。問題文にない規則を勝手に足さず、何を返す探索かを先に読みます。

誤答を直す：並び順のない側を捨てない

配列 12、30、5、24、18 から5を探す場面を考えます。添字は0から4です。「中央の5を見る前に、最初の値12が目標より大きいから右側にはない」と答えるのは誤りです。実際には右側の添字2に5があります。値が昇順なら左の値より右の値が小さくならないといえますが、この列にはその保証がありません。

図3のように、未整列の列では大小だけを根拠に候補を捨てず、線形探索で左から比較します。12、30、5の順に調べ、添字2で見つかるので3回です。ここで示した誤答は、順序の保証を確認しないまま、値の大小から位置まで推測したことが原因です。

もう一つの誤りは、中央が目標と一致しなかった時点で未発見とすることです。中央以外の候補にはまだ目標が残りえます。範囲を更新し、候補が空になるか一致するまで続けます。反対に、空になった後に配列の外の添字を読もうとするのも誤りです。範囲の確認を先に置けば、存在しない要素への比較を防げます。

範囲の更新を言葉で確かめる

二分探索の表を作るときは、各行を「比較前」と「比較後」に分けます。比較前の両端から中央を決め、その中央の値を読みます。値が一致しなければ、初めて次の両端を決めます。更新した後の両端を使って、同じ行の中央を計算し直してしまうと、比較の対象が途中で変わってしまいます。

目標より中央の値が小さい場合、昇順であれば中央の左側の値も中央以下です。そのため、中央とその左側には目標がありません。右側に目標があるとはまだ断定できず、右側を調べる候補として残すだけです。中央の値が大きい場合も同様に、右側を外した後の左側に目標が必ずあるわけではありません。候補が残っていることと発見は区別します。

たとえば、比較前に候補が1個で、その値が目標と一致しなければ、次の候補は空です。このとき空になった理由は、残っていた1個を比較して除いたからです。範囲が空であることを確認してから終了すれば、添字が配列の外へ出るのを防げます。配列の長さが0の場合は、比較を始める前から候補が空なので、反復の本体は1回も実行されません。

線形探索の未発見も、途中で結論を出さずに考えます。調べた要素が一致しなければ次に移り、最後の要素を調べ終えた後に未発見とします。最初の要素で一致する場合は1回で止まり、配列が空なら0回です。こうした端の条件を試すと、追跡表の終了位置が適切かを見直せます。

自分で追う練習

次の4問はそれぞれ独立した自作の配列です。添字は左端を0とし、線形探索は左から、一致した時点で止めます。二分探索は昇順の範囲の両端を含め、中央は添字の和を2で割った整数の商とします。比較回数は要素と目標の照合回数です。各問で、比較した値の順番、結果の添字または未発見、比較回数を答えてください。空の配列では比較した値を「なし」と書きます。

1. 展示札の配列 17、6、28、11 を線形探索し、目標11を探します。
2. 昇順の座席番号 2、7、10、16、22、35、41、50 を二分探索し、目標50を探します。
3. 昇順の整理札 1、5、12、19、27 を二分探索し、目標6を探します。
4. 空の配列を線形探索し、目標9を探します。

練習の答えと確かめ方

1. 比較は17、6、28、11の順で、添字3、4回です。途中の28が11より大きくても、線形探索は並び順を前提にしないので次へ進みます。元の配列の添字3を読むと11です。最後の要素に到達したときも、比較後に一致を確認してから終了します。

2. 比較は16、35、41、50の順で、添字7、4回です。範囲は0から7、4から7、6から7、7から7と変わります。最初の中央は添字3、次は添字5です。いずれも目標より小さいため右側を残し、最後の添字7で一致します。元の配列の右端が50であることも確認できます。

3. 比較は12、1、5の順で、未発見、3回です。範囲は0から4、0から1、1から1と変わります。5は6より小さいので、次は左端2、右端1となり候補が空です。元の列に6がないことを先頭から確認すると、未発見の結論と合います。5と12の間に値が入りうることと、その値が列に存在することは別です。

4. 比較した値はなし、未発見、0回です。要素がないため、最初の要素を読む処理に入れません。元の配列に戻っても調べられる値はなく、比較回数が0であることと矛盾しません。未発見を示す表示と、見つかった添字0を混同しないことも大切です。

手元に残す要点

線形探索は並び順を問わず、端から一致を探します。
二分探索は昇順の候補を中央との比較で狭めます。
候補が空になれば未発見、空の配列の比較は0回です。
添字と値を分け、比較の回数は問題の定義に従います。

どこで止まったかを見分ける

答えの位置は合っていても、途中の範囲に誤りが隠れることがあります。まず本人が書いた表で、比較前の両端と中央を指さし、なぜ片側を外せるのかを説明してみてください。中央の計算で止まる場合は添字を並べて数え、一致後も処理を続ける場合は終了条件に印を付けます。未発見の答えだけが誤る場合は、最後の比較後に左端と右端がどうなったかを確認します。

個別指導では、授業の疑似コードと本人の追跡表を並べ、添字の開始位置、範囲の端、中央の端数処理、比較回数の数え方を1つずつ照合できます。未整列の列と空の列も別々に追い、どの前提がないと範囲を捨てられないかを本人の言葉で説明できれば、初めて見る列でも判断の筋道が残ります。