基本情報技術者試験のサンプル問題（科目B）を解いてみよう。
今回のテーマは、「無限ループ」である。
〔プログラム〕
○整数型: search(整数型の配列: data, 整数型: target)
整数型: low, high, middle
low ← 1
high ← dataの要素数
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 解答群
ア 要素数が1で，targetがその要素の値と等しい
イ 要素数が2で，targetがdataの先頭要素の値と等しい
ウ 要素数が2で，targetがdataの末尾要素の値と等しい
エ 要素に－1が含まれている
※プログラム中の行番号は筆者が追記。
正解：ウ
二分探索とは？
ソート済みの配列に対して、目的の値（target）を効率的に探す方法である。
探索範囲を毎回半分に絞ることで、探索時間を大幅に短縮できる。
コードの流れ
関数 search(data, target)
low ← 1
high ← dataの要素数
while (low ≦ high)
middle ← (low + high) ÷ 2 の商
if data[middle] < target
low ← middle
elseif data[middle] > target
high ← middle
else
return middle
return -1ポイント解説
① 初期設定
- low は探索範囲の下限（最初は 1）
- high は探索範囲の上限（配列の要素数）
② 中央の要素を調べる
- middle ← (low + high) ÷ 2 で中央のインデックスを取得
③ 条件分岐
- data[middle] < target → 探したい値は右側にある → low ← middle
- data[middle] > target → 探したい値は左側にある → high ← middle
- data[middle] = target → 見つかった！ → middle を返す
④ 見つからなかった場合
- while ループを抜けたら -1 を返す（見つからなかった）
⚠️ 注意点
このコードには1つのバグがある。
❌ バグの箇所：
low ← middle
high ← middleこれでは、middle が更新されないので、無限ループになる。
✅ 正しい更新方法これにより、探索範囲が確実に狭まる。
low ← middle + 1
high ← middle - 1✅ 正しい二分探索の例（修正版）
if data[middle] < target
low ← middle + 1
elseif data[middle] > target
high ← middle - 1🎯 結論
このコードは二分探索であるが、探索範囲の更新方法にバグがあるため、正しく動作しない。
プログラムのポイント
- 配列は 昇順に整列されていて、重複なし
- 要素番号は 1から始まる
- search 関数には 不具合あり（探索範囲の更新が low ← middle や high ← middle になっている）
- この不具合により、特定の条件で無限ループになる。
各肢を検討しよう！
選択肢「ア」
要素数が1で、target がその要素の値と等しい。
具体例
data = {42} // 要素番号は 1 から
target = 42探索の流れ
- low = 1, high = 1
- middle = (1 + 1) ÷ 2 = 1
- data[1] == target → 一致 → return 1
結果
→ 正常に探索成功。無限ループにはならない。
選択肢「イ」
要素数が2で、target が data の先頭要素の値と等しい。
具体例
data = {10, 20} // 要素番号は 1, 2
target = 10探索の流れ
- low = 1, high = 2
- middle = (1 + 2) ÷ 2 = 1
- data[1] == target → 一致 → return 1
結果
→ 正常に探索成功。無限ループにはならない
選択肢「エ」
要素に -1 が含まれている。
具体例
data = {-3, -1, 0, 2, 4} // 要素番号は 1〜5
target = -1探索の流れ
- low = 1, high = 5
- middle = 3 → data[3] = 0 → 0 > -1 → high ← 3
- middle = 2 → data[2] = -1 → 一致 → return 2
結果
→ 正常に探索成功。無限ループにはならない。
なぜ「ウ」が無限ループになるのか？
data = {10, 20}
target = 20初回 middle = 1 → data[1] = 10 → 10 < 20 → low ← middle → low = 1（変化なし！）
- 次回も middle = 1 → 同じ処理 → 無限ループ
→ low ← middle + 1 にしないと、探索範囲が狭まらない。
各肢をC言語のコードで確かめよう！
C言語コード（選択肢アの例）
#include <stdio.h>
int binary_search(int data[], int size, int target) {
int low = 0;
int high = size - 1;
int middle;
while (low <= high) {
middle = (low + high) / 2;
if (data[middle] < target) {
low = middle + 1;
} else if (data[middle] > target) {
high = middle - 1;
} else {
return middle; // 見つかった位置を返す
}
}
return -1; // 見つからなかった
}
int main() {
int data[] = {42}; // 要素数1の配列（0始まり）
int size = sizeof(data) / sizeof(data[0]);
int target = 42;
int result = binary_search(data, size, target);
if (result != -1) {
printf("target %d は配列の %d 番目（0始まり）にあります。\n", target, result);
} else {
printf("target %d は配列に存在しません。\n", target);
}
return 0;
}実行結果
target 42 は配列の 0 番目（0始まり）にあります。このコードは、配列の要素数が1つだけで、target がその要素と一致する場合に、正常に探索が成功することを確認するものである。
C言語コード（選択肢イの例）
#include <stdio.h>
int binary_search(int data[], int size, int target) {
int low = 0;
int high = size - 1;
int middle;
while (low <= high) {
middle = (low + high) / 2;
if (data[middle] < target) {
low = middle + 1;
} else if (data[middle] > target) {
high = middle - 1;
} else {
return middle; // 見つかった位置を返す
}
}
return -1; // 見つからなかった
}
int main() {
int data[] = {10, 20}; // 要素数2の配列（0始まり）
int size = sizeof(data) / sizeof(data[0]);
int target = 10;
int result = binary_search(data, size, target);
if (result != -1) {
printf("target %d は配列の %d 番目（0始まり）にあります。\n", target, result);
} else {
printf("target %d は配列に存在しません。\n", target);
}
return 0;
}実行結果
target 10 は配列の 0 番目（0始まり）にある。このコードは、配列の先頭要素が target と一致する場合に、正常に探索が成功することを確認するものである。
選択肢「ウ」の条件
要素数が2で、target が data の末尾要素の値と等しい。
バグありの C言語コード（無限ループになる）
#include <stdio.h>
int buggy_search(int data[], int size, int target) {
int low = 0;
int high = size - 1;
int middle;
while (low <= high) {
middle = (low + high) / 2;
if (data[middle] < target) {
low = middle; // ❌ 本来は middle + 1 にすべき
} else if (data[middle] > target) {
high = middle; // ❌ 本来は middle - 1 にすべき
} else {
return middle;
}
}
return -1;
}
int main() {
int data[] = {10, 20}; // 要素数2（0始まり）
int size = sizeof(data) / sizeof(data[0]);
int target = 20;
int result = buggy_search(data, size, target);
if (result != -1) {
printf("target %d は配列の %d 番目（0始まり）にあります。\n", target, result);
} else {
printf("target %d は配列に存在しません。\n", target);
}
return 0;
}⚠️ 実行時の挙動
このコードを実行すると、以下のような問題が発生する。
- 初回 middle = 0 → data[0] = 10 → 10 < 20 → low = 0（変化なし）
- 次回も middle = 0 → 同じ処理 → 無限ループ突入！
修正すべき箇所
if (data[middle] < target) {
low = middle + 1; // ✅ 正しい更新
} else if (data[middle] > target) {
high = middle - 1; // ✅ 正しい更新
}C言語コード例（選択肢エの例）
#include <stdio.h>
int binary_search(int data[], int size, int target) {
int low = 0;
int high = size - 1;
int middle;
while (low <= high) {
middle = (low + high) / 2;
if (data[middle] < target) {
low = middle + 1;
} else if (data[middle] > target) {
high = middle - 1;
} else {
return middle; // 見つかった位置を返す
}
}
return -1; // 見つからなかった
}
int main() {
int data[] = {-5, -3, -1, 0, 2, 4, 6};
int size = sizeof(data) / sizeof(data[0]);
int target = -1;
int result = binary_search(data, size, target);
if (result != -1) {
printf("target %d は配列の %d 番目（0始まり）にあります。\n", target, result);
} else {
printf("target %d は配列に存在しません。\n", target);
}
return 0;
}実行結果
target -1 は配列の 2 番目（0始まり）にあります。このように、-1 が配列に含まれていても、正しく探索できることが確認できる。
data = [-5, -3, -1, 0, 2, 4, 6]
target = -1この配列は昇順にソートされており、target = -1 は3番目の要素である。
まとめ
擬似コードでは low/high の更新に “±1” が含まれていないため、middle がそのまま代入され、探索範囲が縮まらずループする。
2要素配列 {x, y} に対して target = y の場合、最初の middle = 1 となり、データが小さいので low ← middle = 1 を代入するが、次も同じ状態が続くため無限ループとなる。
コメント