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

武蔵野個別指導塾の特徴

共通テスト情報I 二分探索の整列条件—未整列の列で存在する値を捨てる一手を見つける|武蔵野個別指導塾

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

楽器の長さの列で、中央との比較が目的の位置を捨てる瞬間を追い、未整列の二分探索に注意しましょう。

よくあるのは、高校生が楽器の長さを記録した順のまま二分探索し、列にある長さを「存在しない」と答える場面です。中央の値と探す値の大小を正しく比べても、その一手で目的の位置を捨てることがあります。以下の長さや列は、処理を確かめるための自作の条件です。単位は同じものとして扱い、探すのは値が一致する位置です。

要点(結論から)

  • 範囲の両端と中央の計算を問題の規則で追います。
  • 中央との大小から片側を捨てる根拠は昇順です。
  • 未整列では実際の位置が最初に外れる更新を示します。

どの判断が問われるか

1つ目の型は、探索範囲と中央の位置を順に追い、返される添字を求める問題です。範囲の両端を含むか、中央の端数をどう扱うかで次の比較位置は変わります。実行する前に、問題に指定された規則を読み取ります。

2つ目は、目的の値が列にあるのに見つからない理由を説明する問題です。最後の戻り値だけでなく、実際の位置が探索範囲の外に出た最初の更新を示します。比較の大小が正しくても、範囲を減らす推論の前提が満たされていなければ結果は保証されません。

3つ目は、入力の並びだけを変えて結果を比較する問題です。たまたま中央で一致した未整列の列では成功します。それは未整列でも常に成功する証拠にはなりません。反例は、一般に成り立つという主張を崩すために、条件を満たしながら結論が成り立たない1例です。

捨てる範囲を支える条件

ここでは添字を0から付けます。探索範囲は左端 left から右端 right まで両端を含み、中央 mid は両端の和を2で割った商の整数部分です。空の範囲は left が right より大きい状態です。目的の値を key とし、見つからない場合は有効な添字と区別するため -1 を返します。

図1のように、昇順とは隣り合う値が左から右へ小さくならない並びです。同じ値が隣り合っても昇順です。中央の値が key より小さいなら、昇順の列では中央より左の値も key より小さいため、中央と左側を捨てられます。中央の値が key より大きいときは、中央と右側を捨てられます。

図1 昇順の列で中央との比較から候補を絞る考え方

図1では目的の値は8で、中央の5より大きいため右側を残します。大事なのは、中央と key の大小だけでなく、中央の両側にも昇順という関係が及ぶことです。未整列なら左側に大きい値が隠れることも、右側に小さい値が隠れることもあります。その場合、中央との比較から捨てた側の全要素の大小は決まりません。

探索中に保ちたい性質は「目的の値が存在するなら、その少なくとも1つの位置が現在の範囲に残る」です。重複があるとき、ある1つの位置が消えても別の一致が残れば、この性質はまだ保たれます。以下の基本例は一致が1つなので、その位置が消える一手を明確に指せます。

基本例題:長さの記録順をそのまま使う

長さの列を A = [8, 2, 4, 6, 10]、探す値を8とします。次の自作プログラムを実行したとき、戻り値を整数で答え、実際に8がある添字が範囲から外れる最初の更新を示してください。比較は等しい場合を先に判定します。

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

A = [8, 2, 4, 6, 10]
print(search(A, 8))

実行結果は -1 です。len(a) は要素数、// はこの非負の和について整数部分を取る割り算です。初期化から終了まで、各行の時点を省かずに追います。

時点 left right 判断と次の状態
初期化後 0 4 5要素の全範囲
1回目の条件 0 4 0 <= 4 は真、本体へ
中央と比較 0 4 mid は2、A[2]は4。8と等しくなく、4 < 8 は真
左端の更新後 3 4 left を2 + 1にする。添字0の8が範囲外
2回目の条件 3 4 3 <= 4 は真
中央と比較 3 4 mid は3、A[3]は6。8と等しくなく、6 < 8 は真
左端の更新後 4 4 left を3 + 1にする
3回目の条件 4 4 4 <= 4 は真
中央と比較 4 4 mid は4、A[4]は10。8と等しくなく、10 < 8 は偽
右端の更新後 4 3 right を4 − 1にする
終了判定 4 3 4 <= 3 は偽。-1を返す

図2のように最初の更新前は添字0が範囲内ですが、更新後は範囲が3から4となり、そこに8はありません。実際に A[0] は8なので、戻り値の -1 は列全体に対する未発見という目的に合いません。4 < 8 という比較自体は正しく、間違いの根拠は左側も8より小さいと決めた点です。

図2 未整列の長さの列から目的の位置が外れる最初の更新

この処理は範囲が空になるまで進み、停止します。途中で真の位置を失った後に探索を続けても、その位置を再び候補に戻す命令はありません。終了時に未発見を返すことと、入力全体に値が存在しないことは、前提が崩れた場合には別の事実です。

標準例題:同じ値を昇順に並べた場合

列を B = [2, 4, 6, 8, 10] とし、先ほどの search で8を探します。戻り値と各比較位置を答えてください。列の値は基本例と同じで、順序だけが違います。

初めは範囲0から4、mid は2です。B[2] は6で8より小さいため left は3になります。次は範囲3から4、mid は3で B[3] は8です。一致したので添字3を返します。B[3] が実際に8であることまで戻って確かめられます。

最初に左側を捨てても、昇順なら添字0から2の値は中央の6以下です。8がそこにある可能性はないため、この更新は正当です。両方の列で最初に中央が目的より小さくても、左側の値に関する根拠は異なります。

発展例題:未整列でも成功する場合

C = [7, 1, 9] で1を探す場合と7を探す場合を比べます。戻り値と、成功の有無から言えることを答えてください。いずれも同じ search を使います。

1を探すと、初めの範囲は0から2、mid は1です。C[1] が1なので直ちに添字1を返し、C[1] は目的の値です。一方、7を探すと中央の1が小さいので left は2になります。この更新で唯一の7がある添字0を捨てます。次の C[2] は9で大きいため right は1となり、空の範囲で -1 を返します。

同じ未整列の列でも、目的によって成功と失敗が分かれます。成功例はその実行で一致を見たことを示しますが、別の目的にも範囲縮小が正しいことまでは示しません。失敗例では C[0] が7であるため、未発見という結論が列全体について誤りだと確かめられます。

誤答をどこから直すか

基本例に「中央の4は8未満だから、その左にも8はない」と答えると、比較と列の性質を混同しています。図3のように、左に実際の8がある状態で left を3に更新したところが、目的の位置を失う最初の箇所です。

図3 未整列の列で誤った候補除外と修正方針を対比
見方 判断 修正
誤答 中央が小さいので左側に目的はない 列が昇順かを先に確認する
追跡 添字0に8があり、更新で範囲外になる その更新と失われた位置を示す
別の方法 順序に頼らず列を左から確認する 一致した位置を返し、最後までなければ未発見にする

図3の修正は、未整列の入力をそのまま調べる方法です。左から順に値を調べれば、見つかるまでは位置を飛ばしません。例えば基本例では最初の添字0で8に一致します。昇順であることを入力条件として保証できる場合には元の二分探索を使えますが、記録順のまま保証なしに使うことはできません。並べ替えた列の添字は元の記録順の添字と一致するとは限らないため、位置を答える問題ではどちらの位置かも区別します。並べ替える手順自体はここでは扱いません。

空の列では right が -1となり初回の条件が偽です。そのため -1 を返します。1要素では添字0を比較し、一致すれば0、不一致なら範囲を空にして -1 を返します。これらは探索の端の扱いを確認する入力であり、未整列による誤った除外とは別の確認です。

候補が残ることと見つかること

昇順の列で一致していない中央を捨てるとき、残る候補が必ず目的の値だと言っているわけではありません。残る範囲には異なる値も含まれます。保証するのは、存在する一致を捨てていないという点です。範囲が空になるまで一致しなければ、その保証を根拠に、元の列にも一致がないと結論できます。

一方、未整列の列では、候補が残るという保証が失われても、たまたま残った側で一致する場合があります。したがって、各回の範囲が狭くなり停止することは、結果の正しさとは別の性質です。戻り値が添字の場合はその添字の値を確かめ、-1の場合は入力全体を調べて未発見という結論を検証します。

未発見を返した実行を確認する際には、探索が実際に訪れた位置と、元の列に存在する位置を別に記録します。訪問していない位置を「調べて一致しなかった位置」と見なさないことが、反例を読み取る出発点です。

練習問題

次の5問は自作です。各列の添字は0から、範囲は両端を含み、上の search を使います。値がある位置を答えるときは添字を、未発見は -1 を整数で答えてください。

  1. 展示札の列 [3, 11, 15, 19, 23] から19を探します。比較した添字の順と戻り値を答えてください。
  2. 箱の重さの列 [18, 5, 9] から18を探します。戻り値と、18の位置を初めて範囲外にする更新を答えてください。
  3. 座席番号の列 [14, 2, 20] から2を探します。戻り値と、未整列でも成功した理由を答えてください。
  4. 空の列で12を探す場合と、1要素の列 [12] で12を探す場合について、それぞれ戻り値を答えてください。
  5. 昇順の列 [4, 4, 13, 17, 17] から17を探します。戻り値と、その値が実際に目的に一致するかを答えてください。

練習の答えと追跡

  1. 添字の順は2、3、戻り値は3です。最初の15は19より小さいので範囲を3から4にします。次の添字3は19で、展示札の目的値に一致します。
  2. 戻り値は -1 です。最初の中央は添字1の5で、18より小さいため left を2にします。このとき添字0の18が外れます。残る添字2の9も18より小さく、left が3になって終了します。箱の列には実際に18があるため、未発見は目的に合いません。
  3. 戻り値は1です。初回の中央の添字1が2で、範囲を捨てる前に一致します。座席番号が見つかった事実は確認できますが、未整列の列の他の値も見つかる保証にはなりません。
  4. 空の列は -1、[12] は0です。前者は最初から left が0、right が -1で比較に入りません。後者は中央の添字0に12があり、1回の比較で一致します。空の列に目的の位置はなく、後者の添字0は実際の値を指します。
  5. 戻り値は3です。中央の添字2は13で小さいため、範囲を3から4にします。次の添字3が17で一致します。添字4にも17がありますが、この処理は最初に比較で一致した位置を返し、最後の位置を求める処理ではありません。

要点

追跡のどこを確かめるか

本人が比較した値を正しく書けているのに結論を誤る場合は、追跡表に「更新前の範囲」「実際の一致位置」「更新後の範囲」の列を加えます。更新後の列に実際の位置が残るかを1行ずつ確認すると、計算違いと前提違反による候補の消失を分けられます。

個別指導では、昇順の列と順序を変えた列について、同じ比較結果から捨てた側の値を実際に調べます。重複があるときは一致位置が複数残る可能性も確認します。範囲を半分にする一手の正しさは、列の並びに支えられています。

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

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

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

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

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

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

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