【基本情報技術者試験】C言語で追う！トレース問題（線形探索・二分探索編）

はじめに

前回のバブルソート編では、C言語のコードを使いながら「試験のトレース問題をどう読み解くか」という視点で解説した。今回はその第2弾として、同じくアルゴリズム問題の定番である「線形探索」と「二分探索」を取り上げる。

この2つは、「同じ『探す』という目的を、まったく違うアプローチで実現している」という点が試験でもよく問われる。実際にC言語で動かして、比較回数の違いを目で見て確認してみよう。

今回使うコード「線形探索」・「二分探索」

#include <stdio.h>

#define SIZE 10

void print_array(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

/* 線形探索：先頭から順番に1つずつ比較していく */
int linear_search(int arr[], int size, int target) {
    int comparisons = 0;

    for (int i = 0; i < size; i++) {
        comparisons++;
        printf("  比較%d回目: arr[%d] = %d と %d を比較\n", comparisons, i, arr[i], target);

        if (arr[i] == target) {
            printf("  → 見つかりました（比較回数: %d回）\n", comparisons);
            return i;
        }
    }

    printf("  → 見つかりませんでした（比較回数: %d回）\n", comparisons);
    return -1;
}

/* 二分探索：中央値との比較で探索範囲を半分ずつ絞り込む（配列はソート済み前提） */
int binary_search(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;
    int comparisons = 0;

    while (low <= high) {
        int mid = (low + high) / 2;
        comparisons++;

        printf("  比較%d回目: low=%d, high=%d, mid=%d (arr[mid]=%d) と %d を比較\n",
               comparisons, low, high, mid, arr[mid], target);

        if (arr[mid] == target) {
            printf("  → 見つかりました（比較回数: %d回）\n", comparisons);
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    printf("  → 見つかりませんでした（比較回数: %d回）\n", comparisons);
    return -1;
}

int main(void) {
    int data[SIZE] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 15;

    printf("探索対象の配列: ");
    print_array(data, SIZE);
    printf("探す値: %d\n\n", target);

    printf("[線形探索]\n");
    linear_search(data, SIZE, target);

    printf("\n[二分探索]\n");
    binary_search(data, SIZE, target);

    return 0;
}

両方の関数に comparisons（比較回数）というカウンタを入れているのがポイントである。試験のトレース問題では「何回目の比較で見つかるか」を問われることが多いので、あえてコードの中でカウントして表示するようにしている。

実行結果

配列 {1, 3, 5, 7, 9, 11, 13, 15, 17, 19} から 15 を探す。

探索対象の配列: 1 3 5 7 9 11 13 15 17 19
探す値: 15

[線形探索]
  比較1回目: arr[0] = 1 と 15 を比較
  比較2回目: arr[1] = 3 と 15 を比較
  比較3回目: arr[2] = 5 と 15 を比較
  比較4回目: arr[3] = 7 と 15 を比較
  比較5回目: arr[4] = 9 と 15 を比較
  比較6回目: arr[5] = 11 と 15 を比較
  比較7回目: arr[6] = 13 と 15 を比較
  比較8回目: arr[7] = 15 と 15 を比較
  → 見つかりました（比較回数: 8回）

[二分探索]
  比較1回目: low=0, high=9, mid=4 (arr[mid]=9) と 15 を比較
  比較2回目: low=5, high=9, mid=7 (arr[mid]=15) と 15 を比較
  → 見つかりました（比較回数: 2回）

同じ配列・同じ探す値なのに、線形探索は8回、二分探索は2回という大きな差が出た。この差こそが、試験でも問われる「探索アルゴリズムを使い分ける理由」である。

二分探索のトレースを1行ずつ追う

二分探索の中身をもう少し細かく見てみよう。試験本番のつもりで、low、high、mid の3つの変数がどう変化していくかを表にまとめた。

試験問題では、この表の空欄（low high mid の値や、次にどちらへ絞り込むか）を埋めさせる出題が定番である。ポイントは以下の2つである。

1. mid は (low + high) / 2 の整数除算で求まるため、割り切れない場合は小数点以下が切り捨てられる（今回は (5+9)/2 = 7）
2. arr[mid] と探している値を比較し、大小関係によって low か high のどちらかだけを更新する（両方は動かさない）

試験問題を解くときの読み方のコツ

1. 線形探索は「上から順に見ていくだけ」なので難しくないが、何回目の比較で見つかったかという問いには、ループの中で数え始めが0か1かを間違えないよう注意しよう。
2. 二分探索は、low <= high の条件を満たす間だけループが続くことを押さえておくと、「見つからなかった場合に何回ループが回るか」も計算しやすくなる。
3. 二分探索の前提は「配列がソート済みであること」である。この前提条件そのものを問う設問（「ソートされていない配列に二分探索を適用した場合どうなるか」など）も出題されるので、暗記ではなく仕組みとして理解しておこう。

計算量の比較

データ件数が増えるほど、二分探索の効率の良さが際立つ。例えば要素数が1,000件でも、二分探索なら最大10回程度の比較で見つかる計算になる（$2^{10} = 1024$）。この「なぜO(log n)になるのか」を、比較のたびに範囲が半分になる、という仕組みから説明できるようにしておくと、計算量を問う設問にも対応しやすくなる。

まとめ

• 線形探索と二分探索は、同じ「探す」処理でもアプローチがまったく異なる
• 二分探索は効率が良い一方、「ソート済みであること」という前提条件がある
• トレース問題では、low high mid の変化を表に書き出しながら追うと間違いにくい

この記事で扱ったコードは、GitHubの c-language-studies リポジトリ（FE-algorithm/02_search/c/）で公開している。今後、同じアルゴリズムをGo/Kotlinに移植した比較記事も予定しているので、興味のある方はリポジトリもチェックしていただきたい。