基本情報技術者試験の「科目B」で必ずと言っていいほど出題されるのが、二分探索（バイナリサーチ）のトレース問題です！
「配列の中央インデックス mid の計算で +1 や -1 をする理由がわからない…」
「low や high のポインタがどう移動して範囲が狭まるのか頭の中で追いきれない…」
そんな悩みを持つ未経験・文系受験生のために、当サイトでは1行1処理の厳密なトレース ＆ 探索範囲の縮小が直感的にわかるビジュアルシミュレーターを用意しました！
まずは実際に動かしながら、二分探索の高速なアルゴリズムとプログラムの連動感を体感してみましょう。
1. 【動く図解】ステップ進むボタンでトレースを擬似体験してみよう
下の「進む ➔」ボタンを押すと、実行中のコード行が1行ずつハイライトされ、探索範囲（low〜high）と中央値（mid）の変化がリアルタイムに確認できます。
整列済み配列 num の探索トレース
2. 二分探索（バイナリサーチ）とは？前提条件と仕組み
二分探索（Binary Search）とは、目的のデータを探す際に「配列の中央の値と比較し、探索範囲を毎回半分に絞り込んでいく」アルゴリズムです。
辞書で単語を調べるとき、適当に真ん中のページを開いて「目的の単語より前か後か」で開く範囲を半分にしていく感覚とまったく同じです。
⚠️ 試験で超重要な「絶対条件」
二分探索を実行するには、「データがあらかじめ昇順または降順に並べ替えられている（ソート済みである）こと」が必須条件です。
バラバラに並んだデータに対して二分探索を行うことはできません（バラバラの場合は端から順に探す「線形探索」を使います）。
3. 科目B穴埋めの超頻出！`mid + 1` と `mid – 1` の理由
基本情報技術者試験の穴埋め問題で最も狙われるのが、探索範囲を狭める際の `+1` と `-1` の処理です。
Line 8: low = mid + 1（中央値num[mid]より目的の値が大きい場合、mid自体は探す対象から除外できるため、範囲の左端をmid + 1に移動）Line 10: high = mid - 1（中央値num[mid]より目的の値が小さい場合、範囲の右端をmid - 1に移動）
ここで単に low = mid や high = mid にしてしまうと、値が見つからなかった場合に無限ループに陥る危険があります。
シミュレーターで Line 7➔8 や Line 9➔10 へ進む際、mid の隣へポインタが跳ぶ動きをしっかり確認しておきましょう。
4. 計算量の比較（線形探索 vs 二分探索）
データ件数を $n$ としたとき、探索アルゴリズムの計算量は以下のように大きく異なります。
- 線形探索（Linear Search）: $O(n)$（端から1個ずつ調べるため、100万個なら最大100万回）
- 二分探索（Binary Search）: $O(\log_2 n)$（毎回半分にするため、100万個でもわずか20回程度で発見可能）
この圧倒的なスピードが二分探索の最大の強みです。
5. 二分探索に関するよくある質問（FAQ）
Q. 要素数が「偶数」のとき mid はどう計算されますか？
A. 基本情報の擬似言語では整数割り算（端数切り捨て）を行うため、例えば 0 と 5 の中央は (0 + 5) / 2 = 2 となり、左寄り要素が選択されます。
Q. 探す値が配列内に存在しない場合、プログラムはどう終了しますか？
A. 範囲が狭まり切って low > high の関係が逆転した瞬間、while (low <= high) の条件が不成立となりループを抜けます。
まとめ：範囲を半分に縮めるポインタ処理をマスターしよう
二分探索攻略のポイントは、「中央の計算 ➔ 比較 ➔ mid を除外して探索範囲（low, high）を更新」という3ステップのトレースです。
シミュレーターを動かして `low` と `high` が挟み込まれる感覚を掴み、基本情報科目Bの探索問題を確実に得点源へとしていきましょう！
コメント