冬期講習 2026-2027、募集中。総復習は売りません。90分×完全1対1で、穴だけを塞ぎます 詳しく →
電話 0422-27-7828チャットで質問無料相談を予約

武蔵野個別指導塾の特徴

共通テスト情報I 二分探索の未発見—対象がないとき区間を空にして止める条件を考える|武蔵野個別指導塾

学習のイメージ写真 武蔵野個別指導塾
X LINE Facebook

昇順の歯車径から存在しない値を探し、中央を除く更新と空区間による二分探索の停止をたどりましょう。

よくあるのは、高校生が径の小さい順に並べた歯車の一覧から、指定された径を探す場面です。中央の歯車が目的より小さいので右側に絞ったところ、候補が1個になりました。その歯車も目的と違うのに、中央を候補に残す更新を続けると、同じ歯車を何度も調べてしまいます。見つかる場合の追跡ができても、存在しない場合に処理が終わるとは限りません。

以下の径と配列は、処理を考えるために作った条件です。径の単位はそろっているものとし、比較は整数で行います。目的は、見つかった添字、または見つからなかったことを返す処理を読み、区間が空になるまでの経路を説明することです。

要点(結論から)

  • 候補区間は左右の端を含み、left が right を超えると空です。
  • 不一致の中央は、mid + 1 または mid − 1 の更新で候補から除きます。
  • 一致時はその添字を返し、空になるまで一致しなければ -1 を返します。

何が問われるか

出方の1つは、目的の値がないときに、各回の左右の端と中央を順に記入する問題です。最後の候補が不一致だった後も、次の条件判定まで追います。最後に調べた添字と、終了時の端は別の値です。

もう1つは、更新式の一部が変わった処理について、終了しない入力を挙げる問題です。候補が1個のときに中央自身を残せば、端が変わらない場合があります。長い列で偶然止まった結果だけでは、どの入力でも止まるとは言えません。

さらに、空の列や1要素の列を与え、参照できない添字を使わずに結果が返るかを問う場合もあります。空の列では最初の判定が偽なので、中央の計算も配列の参照も行いません。ここでは昇順の列を前提にし、並べ替え方は扱いません。

候補の両端と空の区間

添字は0から始めます。長さを n とすると、有効な添字は0から n − 1までです。左端を left、右端を right とし、両端を含む候補区間を考えます。初めは left が0、right が n − 1です。left が right 以下なら少なくとも1個の候補があり、left が right より大きければ候補はありません。

図1のように、中央を調べた後は、その比較で目的になり得ない部分と中央自身を除きます。中央の値が目的より小さければ、昇順なので中央より左の値も目的より大きくはなれません。よって left を中央の次にします。中央の値が目的より大きいときは、right を中央の前にします。一致した場合はその添字を返して終了します。

図1 両端を含む候補区間から中央を除く更新

図1では中央が不一致の場合の2通りを示しています。中央を含めて残すと、すでに違うと確かめた位置を再び候補に入れてしまいます。逆に中央の次や前まで一度に捨てると、まだ比較していない位置まで失います。更新する端と、中央からどちらへ1進めるかを組にして覚えます。

区間の長さは、空でない間は right − left + 1です。不一致の更新後は中央が候補から消えるので、この長さが少なくとも1減ります。負にならない整数が減り続けることはできないため、発見しなければやがて空になり、次の判定で止まります。区間が空になったことと、プログラムが途中でエラーを起こしたことは異なります。未発見は最後まで正常に探索した結果です。

重複がある昇順の列でも、以下の処理は一致する位置を1つ返せます。ただし最初や最後の一致位置を保証する処理ではありません。未発見を表す -1 は、この例の有効な添字が0以上であるため、位置と区別できます。別の形式で表す場合は、その問題の約束を確認します。

基本例題:径が一覧にないとき

歯車の径を小さい順に並べた配列を [4, 8, 13, 19, 25] とします。径16を探し、見つかれば添字、なければ -1 を整数で返してください。以下の自作プログラムを用います。a は配列、x は目的の径です。中央の添字 mid は両端の和を2で割った商の整数部分です。返す時点は一致した直後か、反復終了の直後です。

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

print(search([4, 8, 13, 19, 25], 16))

出力は -1 です。len(a) は要素数、// はここでは整数の商です。各代入は右辺を計算してから左辺に保存します。最初の right は4であり、要素数5そのものではありません。

判定の回 判定前 left 判定前 right left <= right mid 中央の径 比較後の更新
1 0 4 真 2 13 13 < 16なので left を3にする
2 3 4 真 3 19 19 > 16なので right を2にする
3 3 2 偽 計算しない 参照しない 反復を抜けて -1 を返す

図2のように、最初に添字2を調べ、次に添字3を調べます。1回目は一致条件が偽、13 < 16が真です。left が3になり、右端4は変わりません。2回目は一致条件も19 < 16も偽なので、else で right が2になります。3回目は left <= right が偽です。ここで初めてループを抜け、末尾の return が実行されます。

図2 径16の探索で候補が空になるまでの変化

図2の最後は「添字3から2まで」の空区間です。添字2の歯車をもう一度調べるのではありません。一覧に戻ると、16は13と19の間に入り、どの径とも一致しません。したがって -1 は歯車が存在しないという場面に合います。実行結果と表が一致しても、表の各値が元の配列を指すかまで確認すると、添字のずれを見つけやすくなります。

標準例題:1個だけの候補

配列 [7] で目的を7とする場合と、目的を9とする場合について、それぞれ返す整数と判定の経路を求めます。初期値は両方とも left が0、right が0です。

目的が7なら、0 <= 0は真、mid は0、a[0] は7です。一致するので0を返します。返却後は下の比較や次の条件判定へ進みません。添字0の歯車が実際に径7であることも確認できます。

目的が9なら、同じ中央の値7は一致せず、7 < 9が真です。left を1にすると right は0のままなので、次の1 <= 0は偽となり -1 を返します。比較した1個が目的でないため、未発見という答えが場面に合います。目的を5に変えると、7 < 5が偽で right が -1になり、やはり区間は空です。左右どちらに移る場合も、最後の中央を除くことが停止に必要です。

発展例題:空と重複を分ける

配列が空の [] のとき、目的を12として返す整数と、配列を参照する回数を求めます。初期値は left が0、right が -1です。最初の0 <= -1が偽なので、本体に入らず -1 を返します。参照回数は0です。空の一覧には目的の径が存在しないため、この結果で合っています。中央を先に求めて配列を参照する手順では、存在しない要素に触れるおそれがあります。

次に [3, 11, 11, 18] から11を探します。初期区間は0から3で、mid は1、a[1] は11なので1を返します。添字2にも11がありますが、この処理は1つ見つけた時点で返ります。戻った添字1の要素が11であることが目的に合うかの確認であり、添字2を返さなかったことは未発見を意味しません。

両者の違いは、空の場合には比較そのものがなく、重複の場合には一致を確認して早く返る点です。どちらも同じ初期化と判定を使います。列が昇順であるという前提は更新の根拠なので、入力がその前提を満たすかも追跡前に確かめます。

誤答はどこで止まるか

「中央が小さいとき left を mid にすれば、中央より右を探せる」という考えは、中央自身も候補に残す点で誤りです。最小の反例として [7] から9を探します。正しい処理と誤った更新を同じ時点で比較します。

時点 正しい更新 誤った更新
比較前 left 0、right 0、mid 0 left 0、right 0、mid 0
7 < 9 の後 left 1、right 0 left 0、right 0
次の判定 偽となり -1 を返す 真となり同じ中央を再び調べる

図3のように、最初に食い違うのは小さい場合の left の更新直後です。誤った側は同じ状態に戻るので、同じ比較と更新を繰り返します。右側の更新を right = mid とする誤りも、[7] から5を探すと同様に止まりません。検証では無限に待たず、比較回数に上限を設けて同じ状態が続くことを確認します。上限に達したという結果自体は未発見の証明ではなく、この例では状態が完全に繰り返されることが根拠です。

図3 最後の候補を残す誤りと中央を除く修正

図3の修正は、左を進めるなら mid + 1、右を戻すなら mid − 1とすることです。ループ条件だけを left < right に変更すれば止まる例もありますが、候補が1個になった時点で調べずに抜けてしまいます。たとえば [7] から7を探しても最初の条件が偽になり、誤って -1 を返します。停止と正しい結果の両方を確かめる必要があります。

範囲外の添字を読む例外、空の入力、結果が存在しない入力、同じ状態の繰返しは別々の現象です。外部から不正な形式のデータが渡された場合も、昇順の整数配列という前提を満たすかは別途確かめる必要があります。ここに示した関数は入力の検証や時間切れの処理を実装していないため、それらを未発見の -1 と同一視しません。

練習:先に5問

次の各問では、上の search と同じ規則で探索します。配列の添字は0から、候補区間は両端を含みます。各問の数値は自作の条件です。

  1. 長さの順の棒 [2, 6, 10, 14, 20, 24, 28] から14を探します。返す添字と比較した添字を答えてください。
  2. 容量の順の容器 [5, 12, 17, 23, 30, 36] から23を探します。返す添字と比較した添字を順に答えてください。
  3. 昇順の札 [1, 9, 15, 21, 27] から18を探します。返す整数と、各比較後の候補区間を順に答えてください。
  4. 長さの順の板 [32] から29を探します。返す整数と終了時の左右の端を答えてください。
  5. 部品の一覧 [] から41を探します。返す整数と、中央の要素を読む回数を答えてください。

練習の答えと確認

  1. 初期区間は0から6、mid は3です。添字3の値14が一致するため、比較した添字は3、返す添字も3です。棒の一覧の添字3は実際に14です。
  2. 初期区間0から5の mid は2で、値17は23より小さいので左端を3にします。区間3から5の mid は4、値30は大きいので右端を3にします。区間3から3の mid は3で値23と一致します。比較した添字は2、4、3の順で、返す添字は3です。容器の添字3に目的の容量があります。
  3. 初期区間0から4の mid は2、値15は18より小さいので区間3から4です。mid は3で値21は大きく、区間3から2となります。次の判定は偽で、返す整数は -1です。18は15と21の間にあり、一覧にないこととも一致します。
  4. 0から0の中央は0、値32は29より大きいため右端を -1にします。終了時は左端0、右端 -1で、返す整数は -1です。板の唯一の長さは32なので、29はありません。
  5. 最初から左端0、右端 -1で、条件が偽です。中央の要素を読む回数は0、返す整数は -1です。部品がない一覧で目的が見つからないことに対応します。

発見する1と2では、返された添字を配列に戻して目的の値と照らしました。未発見の3から5では、候補が空になった経路と元の一覧の両方を照合しました。途中で例外が起きたり更新が進まなかったりした場合には、この未発見の答えを得たことにはなりません。

要点

追跡表のどこを見るか

お子さまが未発見の答えを出せない場合は、まず各回の判定前の left と right の列を見ます。最後の候補が1個になった行で両端が等しいことを読み取れているか、次に中央の値との比較結果が正しいかを分けて確かめます。中央を除いた後の端だけが誤っていれば、比較の理解と更新式の理解は別の課題です。

個別指導では、一致して返る入力と一致せず空になる入力を同じ表の形式で書き、return と次の条件判定のどちらへ進むかを確認します。空の入力では mid の欄を空けた理由も説明してもらいます。停止した時点の端と最後に調べた位置を区別できれば、見つからない径についても根拠を持って答えられます。

もう「日東駒専」を目標にしないでください。

武蔵境駅徒歩30秒、講師1人に生徒1人の完全1対1。授業のあいだ、先生は隣を離れません。いまの詰まりを、無料相談でそのまま話してください。

まず15分だけ電話で話したい方は、無料電話相談(15分)から。塾からお電話を差し上げます。

本気になった日が、入塾の日。

お子様の教育、迷ったら「丸投げ」してください。必ず、期待以上の結果で返します。武蔵野で育む、武蔵境で学ぶ。

電話は年中無休。365日、24時間、お電話可能。

チャットで質問チャット
無料相談を予約する 電話 0422-27-7828電話 LINE チャット
で質問