最終更新日:2026年10月22日
fe fe-technology algorithm pseudocode trace
まず結論
無限ループを見抜くには、終了条件を確認したうえで、次の判定に向けて変数や状態が変化するかを調べます。
特に注意したいのが、「代入文がある」ことと「値が変わる」ことは別という点です。科目Bでは、全ての選択肢を長く追う前に、同じ状態へ戻る条件がないか探すと効率的です。
直感的な説明
出口へ進みたいのに、毎回同じ位置で足踏みしている状態を想像してください。
位置を更新する
↓
「今いる場所」を、再び「今いる場所」にする
↓
次の判定でも位置は変わらない
↓
同じ処理を繰り返す
プログラムにも、次のような更新が出てきます。
low ← middle
これだけでは誤りとは言えません。しかし、low = middle のときは、代入しても low が変わりません。
ループが終わる方向へ進んでいるかを見ることがポイントです。
定義・仕組み
まず「終了」と「更新」を分けて考える
while (low ≦ high)
... 条件による分岐 ...
low ← middle または high ← middle
endwhile
このような処理は、次の順で読みます。
- 終了条件:
low > highならwhileを抜ける。途中でreturnする場合もある。 - 更新する変数:
lowとhighが探索範囲を決める。 - 更新後の状態:
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 の値を追えます。
触って確認:無限ループになる二分探索
「不具合あり」と「修正後」で、探索範囲が変わるかを比較します。
まず探索範囲の中央を確認します。
まだ比較していません。
見るポイント:同じ 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回:気づいた規則を使い、次の選択肢を効率的に切る。