高校情報I 二分探索—整列済みの範囲を狭めて終了条件と更新を確かめる｜武蔵野個別指導塾

昇順の寸法表で左右の端と中央を動かし、未発見でも候補が減って停止する理由を確かめられます。

よくあるのは、整理済みの寸法表で中央の位置を残したまま範囲を更新し、同じ場所を繰り返し調べてしまう場面です。中央を調べた後にどの位置を残すかを決めると、見つかる場合だけでなく、表にない寸法を探す場合にも処理を終えられます。

寸法表への問いを決める

二分探索の問題には、中央と両端の値を順に追う問い、更新式の誤りを直す問い、未発見まで含めた処理を作る問いがあります。どれも先に、表の順序と探索する範囲を確認します。中央の値と目的の値の大小から、片側を一度に候補から外せることが理由です。

ここでは整数の寸法が小さい順に並ぶリストを使います。同じ寸法が続いても構いません。位置は0から始め、両端を含む区間を調べます。見つかれば一致した位置のどれかを整数で返し、なければ位置として使わない整数の-1を返します。重複の最初や最後は保証しません。空のリストも有効な入力です。

比較回数が必要なときは、中央の要素と目的値を調べた回数とします。等しいか、小さいかという式の評価回数ではありません。リストは探索中に変更しません。この約束がなければ、同じ位置を返しても正しいかどうかを判定できません。

候補を残す区間

左端をleft、右端をrightとし、leftからrightまでを候補とします。要素数がnなら最初はleftが0、rightがn − 1です。空ならrightは-1なので、最初から候補がありません。leftがright以下の間だけ中央を調べます。中央midは両端の和を2で割った商です。端を含むので、候補が1個ならleft、mid、rightは同じです。

図1のように、中央が目的値より小さければ、昇順という前提から中央とその左には目的値がありません。中央の右隣から右端までを残します。中央が大きい場合は中央の左隣までを残します。一致すればその位置を返します。

図1の左右の区間は、比較後の候補です。中央を次の区間に含めないのは、その値が一致しないと既に確認したからです。同じ値が複数あっても、小さい中央の左側や大きい中央の右側に目的値がない理由は変わりません。

反復の前と各更新後に保ちたい条件は、「目的値が表にあるなら、一致する位置が少なくとも1つ候補区間にある」です。初めは表全体が候補なので成立します。不一致で捨てる側には一致がないため、更新後も成立します。leftがrightを超えたら候補は空です。そこでこの条件から一致がないと判断できます。

不一致のたびに中央を区間から除くので、候補の個数は必ず減ります。個数は負にならず有限ですから反復は止まります。一致したときも直ちに戻ります。これは幾つかの入力を試すこととは別の、一般の入力に対する理由です。昇順でない表では捨てた側に目的値が残ることがあり、この説明は成立しません。

基本例題: 目的の寸法を探す

寸法表 [4, 9, 13, 18, 25, 31, 40] から18を探します。位置を整数で答え、中央との比較回数も答えてください。手で見ると18は位置3にあり、最初の中央も位置3です。期待する答えは位置3、比較1回です。

図2のように最初の区間は位置0から6で、中央は3です。中央の値18が目的と一致しますから、他の位置に移る必要はありません。戻った位置の値を表に戻して調べても18です。

次の関数は位置と比較回数を組にして返します。出力の組は、先に位置、次に回数です。関数を定義した後の1行は基本例を実行して表示します。

def search(a, target):
    left = 0
    right = len(a) - 1
    count = 0
    while left <= right:
        mid = (left + right) // 2
        count += 1
        if a[mid] == target:
            return (mid, count)
        if a[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return (-1, count)

print(search([4, 9, 13, 18, 25, 31, 40], 18))

defで表と目的値を受け取ります。leftとrightに候補の両端を置き、countを0にします。whileは候補が残る間の条件です。midを計算したら、その要素を調べるためcountを1増やします。一致なら位置と回数を返します。一致せず中央が小さいなら左端をmidの次へ移し、そうでなければ大きいので右端をmidの前へ移します。候補がなくなったときは最後のreturnで-1と回数を返します。

Python 3.14.8で上の入力を実行した期待値と実際の出力はいずれも (3, 1) です。左右の更新を通らない例だけでは、更新式が正しいかは調べられません。次に複数回の探索と未発見を追います。

標準例: 表にない寸法

同じ表で20を探し、位置と比較回数を答えます。手で表の全要素を見れば20はないので、期待する位置は-1です。中央の位置と値は順に3と18、5と31、4と25です。18は20より小さいので区間は4から6、31は大きいので4から4、25も大きいので4から3になります。候補が空になり、結果は (-1, 3) です。

Python 3.14.8で同じ関数に表と20を渡した実際の出力も (-1, 3) でした。各回で調べた中央は次の区間に残りません。最後にleftが4、rightが3になったことを確かめてから-1を返すため、末尾の位置を未発見の答えと取り違えません。

目的値が表の最小値より小さい場合も、最大値より大きい場合も、同じ更新規則で空の区間に至ります。値の大小だけで捨てる側を決めるので、隣接する寸法の差が一定である必要はありません。ただし最初に昇順かを検査する処理は、この関数には含めていません。整列していない入力は仕様外で、正しい結果を保証しません。

発展例: 重複と端の条件

[5, 12, 12, 12, 27, 35] から12を探します。最初の区間は0から5、中央は2で値は12です。期待値と実際の出力は (2, 1) です。位置1や3も一致しますが、この実装は最初に見た位置2を返します。位置2の値を表に戻しても12なので、任意の一致という約束に合います。

最初の一致位置を必ず返す仕様に変えるなら、一致した位置を記録しながら左側にも一致があるかを調べる必要があります。その変更は戻り値の意味と終了までの比較回数を変えるため、単に「どれかを返す」処理と区別します。空の表では中央を計算せず (-1, 0)、[16] から16を探すと (0, 1)、[16] から17を探すと (-1, 1) です。1個の候補も調べられるよう、条件に等号が必要です。

空の表と単一要素についてもPython 3.14.8で実行し、期待値と実際の出力がそれぞれ上の組で一致しました。空の場合には要素へアクセスしないため、存在しない位置を読み出しません。単一要素の不一致では、中央を除いて候補が空になります。

誤った更新を追って直す

例えば不一致で中央が小さいときに left = mid とすると、中央を候補に残してしまいます。表 [4, 9, 13, 18, 25, 31, 40] から20を探す途中で区間が3から4になったとします。中央は3で値18なので、この誤った更新後も左端は3です。次の中央も3になり、同じ状態から抜け出せません。

図3のように、正しくは左端を4へ進めます。図3の修正後は位置4の25を調べ、大きいので右端を3へ移します。候補が空になり未発見です。この誤例は無制限に実行せず、同じ状態が繰り返されることを有限の追跡で確かめます。

誤答の原因は、中央を調べ終えた事実を更新に反映しないことです。修正は left = mid + 1 です。右側も対称に right = mid - 1 とします。修正後の関数を元の入力で再実行すると (-1, 3) となり、表に20がないという手の確認と一致しました。最後の1個を探す場合まで再確認すると、停止だけでなく一致の取りこぼしも検査できます。

練習: 先に自分で範囲を動かす

各問は昇順の表とし、位置は0始まり、区間の両端を含みます。重複時は上の関数が返す位置を求めます。比較回数は中央の要素を調べた回数で、答えは位置と回数の組です。空の表も扱い、未発見は-1とします。

1. 部品表 [2, 6, 11, 17, 24] から24を探します。
2. 長さの表 [3, 8, 14, 21, 29, 36] から10を探します。
3. 記録表 [7, 15, 15, 15, 22] から15を探します。
4. 空の表から19を探します。
5. 一件の表 [28] から27を探します。

練習の答えと照合

1. (4, 3) です。区間0から4の中央2の11、区間3から4の中央3の17、区間4から4の中央4の24を調べます。位置4に戻ると値は24です。
2. (-1, 3) です。中央2の14は大きく、次の中央0の3は小さく、中央1の8も小さいため候補が空です。表を順に見ても10はありません。
3. (2, 1) です。中央2の値が15なので直ちに返します。位置1と3にも15がありますが、どれか1つという条件に位置2は合います。
4. (-1, 0) です。最初から左端0が右端-1を超え、比較しません。空の表に19はありません。
5. (-1, 1) です。位置0の28を調べると27より大きく、右端が-1になって止まります。表に27はありません。

Python 3.14.8で上の関数に各表と目的値を渡した実際の出力は、順に (4, 3)、(-1, 3)、(2, 1)、(-1, 0)、(-1, 1) でした。期待値も同じです。位置を返した場合はその位置の値が目的値に一致し、-1の場合は表を先頭から見ても一致がないことを別に確かめました。

成功する入力だけでなく、未発見、空、1件の不一致も同じ関数で検査しました。探索が見つからないことは正常な結果で、例外ではありません。一方、昇順でない表や整数以外の混在は前提外です。この関数はそれらを検査して例外に変換しません。外部の道具や時間制限を使う処理でもないため、通信失敗や時間切れの戻り値は定めていません。実行環境自体の失敗は探索結果の-1と区別します。

前提が崩れる場合の見直し

昇順でない例として [10, 2, 8] から10を探すことを考えます。中央の2は10より小さいので、この手順は左側を捨てます。しかし位置0には10があります。探索を続けると8も小さく、未発見と返します。実際には値があるので誤った結果です。これは関数の約束を満たさない入力を使った結果であり、未発見の正常な例とは分けて考えます。Python 3.14.8で実行した期待値と実際の出力はともに (-1, 2) でした。表を直接見ると位置0に10があり、前提違反による取りこぼしも確かめられます。

入力の順序が不明な場面では、探索前に順序を確認するか、昇順に並べ直す必要があります。並べ直した場合、得られる位置は並べ直した後の表の位置です。元の位置が必要なら、値と元の位置を対応させて保存するなど、別の仕様を用意します。探索だけの回数と準備に要する作業を混同しないことも大切です。

比較回数が0の未発見と、比較後の未発見は、同じ-1でも途中の状態が違います。空の表では候補を調べる操作がなく、1件の表ではその1件を調べて初めて候補を外せます。両方を試すと、反復条件と更新のどちらに誤りがあるかを切り分けやすくなります。

要点を残す

• 昇順と、両端を含む候補区間を先に決めます。
• 一致しない中央は次の候補から除きます。
• 候補が空なら未発見、一致ならその位置を返します。
• 反復ごとに候補が減るので有限回で止まります。
• 重複時の優先規則と比較回数の数え方を明記します。

どこでつまずいたかを見分ける

答えが1つずれるときは、位置を0から数えたか、右端を含むかを処理表で確認します。見つからない入力で止まらないときは、連続する2行のleft、right、midを比べます。区間が同じなら、中央を残す更新がないかを調べます。

個別指導では、本人に候補を外す理由を表の順序に結びつけて説明してもらい、次に1件の不一致と空の表を手で追います。結果だけが合う場合も、捨てた側に目的値がない理由を言えるかを確かめます。探索区間の変化を言葉と位置の両方で追えば、停止と未発見の根拠が見えてきます。