基本情報技術者試験のサンプル問題を解こう!(15)(科目B)「無限ループ」

スポンサーリンク
IT系

基本情報技術者試験のサンプル問題(科目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

 探索の流れ

  1. low = 1, high = 1
  2. middle = (1 + 1) ÷ 2 = 1
  3. data[1] == target → 一致 → return 1

結果

→ 正常に探索成功。無限ループにはならない

選択肢「イ」

要素数が2で、target が data の先頭要素の値と等しい。

具体例

data = {10, 20}  // 要素番号は 1, 2
target = 10

探索の流れ

  1. low = 1, high = 2
  2. middle = (1 + 2) ÷ 2 = 1
  3. data[1] == target → 一致 → return 1

結果

→ 正常に探索成功。無限ループにはならない

選択肢「エ」

要素に -1 が含まれている。

具体例

data = {-3, -1, 0, 2, 4}  // 要素番号は 1〜5
target = -1

探索の流れ

  1. low = 1, high = 5
  2. middle = 3 → data[3] = 0 → 0 > -1 → high ← 3
  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 を代入するが、次も同じ状態が続くため無限ループとなる。

コメント

タイトルとURLをコピーしました