Skip to the content.

最終更新日:2026年10月22日

まず結論

無限ループを見抜くには、終了条件を確認したうえで、次の判定に向けて変数や状態が変化するかを調べます。

特に注意したいのが、「代入文がある」ことと「値が変わる」ことは別という点です。科目Bでは、全ての選択肢を長く追う前に、同じ状態へ戻る条件がないか探すと効率的です。

直感的な説明

出口へ進みたいのに、毎回同じ位置で足踏みしている状態を想像してください。

位置を更新する
  ↓
「今いる場所」を、再び「今いる場所」にする
  ↓
次の判定でも位置は変わらない
  ↓
同じ処理を繰り返す

プログラムにも、次のような更新が出てきます。

low ← middle

これだけでは誤りとは言えません。しかし、low = middle のときは、代入しても low が変わりません。

ループが終わる方向へ進んでいるかを見ることがポイントです。

定義・仕組み

まず「終了」と「更新」を分けて考える

while (low ≦ high)
    ... 条件による分岐 ...
    low ← middle  または  high ← middle
endwhile

このような処理は、次の順で読みます。

  1. 終了条件:low > high なら while を抜ける。途中で return する場合もある。
  2. 更新する変数:low と high が探索範囲を決める。
  3. 更新後の状態:low、high が変わらず、同じ分岐になることはないか。

「終了条件が存在するから、いつか終了する」とは限りません。終了条件に到達できない場合があります。

二分探索の短い例

昇順の配列 data = [3, 8] から target = 8 を探します。以下の疑似言語では要素番号は1から始まります。

low ← 1
high ← 2
while (low ≦ high)
    middle ← (low + high) ÷ 2 の商
    if (data[middle] < target)
        low ← middle
    elseif (data[middle] > target)
        high ← middle
    else
        return middle
    endif
endwhile
return -1

初回は middle = (1 + 2) ÷ 2 の商 = 1 です。

data[1] = 3 < 8 なので low ← middle を実行しますが、low は 1のまま。high も2のままです。次回も同じ位置を調べるため、処理が進みません。

回数 low high middle 結果
1回目 1 2 1 low ← 1(変化なし)
2回目 1 2 1 また同じ更新
3回目以降 1 2 1 同じ状態の繰返し

一度確認した中央の要素が不一致なら、次回の候補から外します。この例では low ← middle + 1 と修正すると、次は low = 2 となり、data[2] = 8 を見つけて終了します。

科目Aでどう出る?

繰返し処理の基本知識として、while は処理の前に条件を判定することを押さえます。初回から条件が偽なら0回で終了します。

一方、return や break などによる途中終了がない場合、while の継続条件が真のままなら繰り返します。上の二分探索の修正後は、low = high = 2 で継続条件は真ですが、値が一致したときの return で関数が終了します。前判定・後判定の違いは制御構造の記事で確認できます。

科目Bでどう使う?

1. 具体例で発見 → 次は更新条件から絞る

慣れないうちは、実際に値を代入して2~3回追う方法で問題ありません。変数が変化しないと気づいたら、なぜ変化しないのかを式に戻って確認します。

low ← middle
      ↑
  low と middle が等しい場合は変化しない

この条件を先に見つけられるようになると、すべての選択肢に配列の値を仮定する必要がなくなります。

2. 不具合あり/修正後を切り替えて比べる

次の図解は、配列 [3, 8]、探す値 8 に固定しています。「次の比較」を押すと、中央の要素と low・high の値を追えます。

触って確認:無限ループになる二分探索

「不具合あり」と「修正後」で、探索範囲が変わるかを比較します。

data[1]3候補
data[2]8target
low = 1 high = 2 middle = ― 比較 = 0回

まず探索範囲の中央を確認します。

まだ比較していません。

見るポイント:同じ low・high・middle で同じ比較が繰り返されるか。無限実行はせず、2回の比較で再発を表示します。

3. 変数が一つ変われば必ず終了する、とは限らない

例えば x が 1 → 2 → 1 → 2 と変わる処理も、条件次第では終了しません。

したがって、確認すべきなのは単独の変数の変化だけでなく、次に同じ処理を決める状態が再び現れるかです。

同じ入力条件・同じ状態で、以後の動作が決まる処理なら、その状態に戻った時点で同じ動きを繰り返します。

Pythonで安全に再現する

普段Pythonを使う場合は、検証回数に上限を設けて確かめられます。Pythonの添字は0からなので、上の疑似言語とは番号が1ずれる点に注意してください。

def trace(data, target, fixed=False):
    low, high = 0, len(data) - 1
    seen = set()

    for _ in range(4):  # 無限実行を避ける
        if low > high:
            return -1  # 見つからない
        if (low, high) in seen:
            print("同じ探索範囲が再登場")
            return None
        seen.add((low, high))

        middle = (low + high) // 2
        print(f"low={low}, high={high}, middle={middle}")
        if data[middle] == target:
            return middle
        if data[middle] < target:
            low = middle + 1 if fixed else middle
        else:
            high = middle - 1 if fixed else middle

    return None  # 4回で打ち切り


print(trace([3, 8], 8))              # 同じ範囲を検知 → None
print(trace([3, 8], 8, fixed=True))  # 見つかる → 1

この例で None は「繰返し状態を検知した/上限に達した」という検証用の値です。問題文の「見つからなければ -1」と混同しないでください。

よくある誤解・混同

誤解 正しい見方
代入があるので毎回値は変化する low ← middle でも、両者が等しければ変化しない
while に終了条件があるから必ず止まる return などの途中終了がなければ、継続条件が真のままでは繰り返す
値が変わっていれば無限ループではない 複数の状態を循環する場合もある
二分探索で不一致の中央要素を残してよい 一般的な両端を含む区間では、middle ± 1 で除外する
見つからないときだけ無限ループになる 探す値が存在しても、到達できずに止まる場合がある

一般的な二分探索の前提と動作は二分探索の記事で、代入や分岐の読み方は疑似言語の読み方で確認できます。

まとめ(試験直前用)

  • 終了条件:継続条件が偽になる場合と、return・break などの途中終了を確認する。
  • 更新処理:代入後に実際の値や探索範囲が変化するか確認する。
  • 同じ状態:同じ判定と更新を繰り返す条件を探す。
  • 具体例は2~3回:気づいた規則を使い、次の選択肢を効率的に切る。

© 2024-2026 stemtazoo. All rights reserved.