線形探索と二分探索｜100万件が20回で終わる理由と、それでも線形探索が勝つ場面

こんにちは、数強塾代表の藤原進之介です。この記事は参考書『藤原進之介の最強120講義』の第55講「線形探索と二分探索」のWeb版です。共通テスト「情報Ⅰ」での重要度はA（頻出。得点差がつく）、情報Ⅱでの接続先は(4)情報システムとプログラミングおよび(3)情報とデータサイエンスです。

探索は「線形探索は遅い、二分探索は速い」で終わらせてしまう人が多い単元です。しかしそれだけを覚えて試験に行くと、比較回数を数える問題で必ず手が止まります。この講ではなぜ半分ずつ捨てられるのかを原理から示し、同時に二分探索が勝てない場面を数字で出します。なお、流れ図と3つの制御構造は第47講「アルゴリズムと流れ図」、プログラムを手で追うトレースの技術は第54講「プログラムのトレース」で扱いました。本講は探索アルゴリズムそのものに絞ります。

1. この講の問い

100万件のデータから1件を探すのに、二分探索はなぜ20回で終わるのか。そして、それでも線形探索のほうが速い場面があるのはなぜか。

2. 結論

3. なぜそうなるのか

3-1. 「半分捨てる」とはどういうことか

線形探索は、先頭から順に1つずつ比べていく方法です。1回比較して外れたときに減る候補は1件。n件あれば最悪n回かかります。

二分探索は、真ん中を1回だけ見ます。真ん中の値が探したい値より小さいと分かった瞬間、真ん中より左側は一度も見ずに全部捨てられる。なぜ見ずに捨ててよいのか。配列が昇順に並んでいるので「左側は真ん中よりさらに小さい」と断言できるからです。つまり二分探索の速さはアルゴリズムの巧妙さではなく、あらかじめ整列されているという情報を使い切っていることから来ています。

1回で半分になるなら、最悪の比較回数は「nを何回半分にすれば1になるか」で決まります。

一般に floor(log₂ n) + 1 回（log₂ n の小数を切り捨てて1を足す）。この式は覚えるものではなく、上の表を書けば作れるものです。

では100万件のときは何回か。自分で計算してみてください。 必要なのは2のべき乗だけです。

1,024を1,000とみなす近似は、データ量や通信量の計算でも同じ形で出てきます（第73講「通信速度とデータ量の計算」）。

3-2. 二分探索は「並んでいること」を借金している

ここが本講のいちばん大事なところです。文部科学省の「情報Ⅰ」教員研修用教材が、そのまま釘を刺しています。

国の教材の段階で「速い＝良い、ではない」と明言されています。ではその「並べ替えのコスト」はどれくらいか。同じ教材が載せている選択ソートの比較回数を私の手元で数えたところ、n(n−1)/2 回でした（n=7で21回、n=1,000で499,500回、n=10,000で49,995,000回。実行して式と完全一致を確認）。そこで「そのデータを1回しか探さない」場合を比べます。

500倍の負けです。 1回しか探さないなら、整列などしないで先頭から見ていったほうが圧倒的に速い。「二分探索のほうが優れている」という言い方が成立しないことが、これで数字として見えます。

では何回探せば逆転するのか。同じ配列を k 回探すとして、線形の最悪 k×n と、整列 n(n−1)/2 に二分 k×(floor(log₂ n)+1) を足したものを比べます。私が計算したところ、

• n = 100 → k ≧ 54 回で整列が有利
• n = 1,000 → k ≧ 505 回で整列が有利
• n = 10,000 → k ≧ 5,007 回で整列が有利

だいたい n/2 回です。「同じデータを、要素数の半分くらいの回数以上探すなら、並べ替える価値がある」。この見立てを持っておくと、試験でも実務でも判断を誤りません。逆に言えば、1回きりの検索に凝ったアルゴリズムを持ち込むのは、たいてい遅くなります。

3-3. 境界条件を1つ間違えると壊れる

二分探索は短いのに事故が多いアルゴリズムです。事故の場所はほぼ2か所に決まっています。

(a) ループ条件の等号。 「下限 ≦ 上限 の間くり返す」と書くべきところを「下限 < 上限」と書いてしまう間違いです。教員研修用教材は、ここに注記を置いています。

読み替えると、下限と上限が一致した「残り1件」の状態も、まだ調べ終わっていないということです。人間は「1件しか残っていないならそれが答えだ」と飛ばしますが、機械は比較して初めて答えを確定します。だから等号が要る。等号を落とすと、その最後の1件を見ずに「見つかりませんでした」と答えます。

(b) 範囲の更新の +1。 「下限 = 中央 + 1」と書くべきところを「下限 = 中央」にしてしまう間違いです。こうすると範囲が縮まらない場合が生じ、永久に終わりません。

この2つは症状が正反対です。等号落ちは黙って間違った答えを出す。+1落ちは止まらない。試験でも実務でも怖いのは前者です。4-4で両方を実際に動かしてみます。

3-4. 中央の求め方にも流儀がある

中央の添字は「(下限 + 上限) ÷ 2 の小数点以下切り捨て」で求めます。ここで細かい話をひとつ。教員研修用教材のPythonは m = int((i+j)/2)、大学入試センターが示すPython対比例は (hidari+migi)//2 と書いています。高校で扱う大きさではどちらも同じですが、私が試したところ i = 10¹⁷、j = 10¹⁷+2 では前者が 100000000000000000、後者が 100000000000000001 とずれました（浮動小数点の精度が足りなくなるため）。試験では気にしなくてよい。実装では //（整数除算）が正しい。

なお、二分探索を「O(log n)」というオーダー記法で表す書き方は、高校の一次資料には出てきません。 学習指導要領解説 情報編、情報Ⅰ教員研修用教材 第3章、情報Ⅱ教員研修用教材のいずれにも「計算量」という語が1件も無いことを、私が全文検索で確認しました（2026年8月3日）。記法の話は本書の第57講に譲り、本講は比較回数という具体的な数だけで通します。

4. 手で確かめる

4-1. 教材と同じ配列で、両方の比較回数を数える

教員研修用教材が二分探索の説明に使っている配列 a = [25, 33, 43, 51, 66, 71, 88]（7個、昇順）を使います。この7つの値を1つずつ探したときの比較回数を、実際にプログラムを走らせて数えました。

ここで探索値25の列を見てください。線形1回に対し、二分3回。線形探索の勝ちです。 探している値が先頭付近にあるなら、真ん中から始める二分探索はむしろ回り道になります。「二分探索は常に速い」が誤りであることが、教材が選んだ配列そのもので確認できてしまいました。

ちなみに存在しない値（10・60・100）で試すと、線形はいずれも7回、二分はいずれも3回でした。見つからない場合こそ、二分探索の強みが出ます。

4-2. 探索範囲が半分になる様子を図で見る

配列 Ten = [12, 25, 38, 44, 57, 63, 79, 86]（8個）から 57 を探します。範囲がどう縮むかを描きました。

3回目に注目してください。下限と上限が同じ添字4になっています。 人間の目には「もう57しか残っていない」と見えますが、機械はまだ比較していません。ここで「下限 < 上限」を条件にしていたら3回目が実行されず、57は見つからずに終わります。3-3で引用した教材の注記は、まさにこの1コマの話でした。

4-3. 共通テスト用プログラム表記で書く

同じ処理を、共通テストで使われる表記で書きます。文法は大学入試センターが公表している「共通テスト用プログラム表記の例示」で1つずつ裏を取りました（配列名は先頭が大文字、添字は0から、整数の商は ÷、繰返しは「〜の間繰り返す:」、制御範囲は縦棒とかぎ記号で表す、など）。以下は私が自作した例です。

Ten = [12,25,38,44,57,63,79,86]
kazu = 要素数(Ten)
atai = 57
hidari = 0 , migi = kazu - 1
owari = 0 , kaisu = 0
hidari <= migi and owari == 0 の間繰り返す:
｜ aida = (hidari + migi) ÷ 2     # ÷ は商の整数値
｜ kaisu = kaisu + 1
｜ もし Ten[aida] == atai ならば:
｜ ｜ 表示する(atai,"を",kaisu,"回で発見。添字は",aida)
｜ ｜ owari = 1
｜ そうでなくもし Ten[aida] < atai ならば:
｜ ｜ hidari = aida + 1
｜ そうでなければ:
⎿ ⎿ migi = aida - 1
もし owari == 0 ならば:
⎿ 表示する(atai,"は見つかりませんでした")

このコードをPythonに書き写して実行し、出力が図と一致することを確認しました。

Ten = [12,25,38,44,57,63,79,86]
atai = 57
hidari = 0
migi = len(Ten) - 1
owari = 0
kaisu = 0
while hidari <= migi and owari == 0:
    aida = (hidari + migi) // 2
    kaisu = kaisu + 1
    if Ten[aida] == atai:
        print(atai, "を", kaisu, "回で発見。添字は", aida)
        owari = 1
    elif Ten[aida] < atai:
        hidari = aida + 1
    else:
        migi = aida - 1
# atai = 57 のときの出力
# 57 を 3 回で発見。添字は 4

この配列で8つの値をすべて探すと、二分探索の比較回数は 3, 2, 3, 1, 3, 2, 3, 4（合計21・平均2.625）、線形探索は 1〜8（合計36・平均4.5）でした。最大は4回で、floor(log₂ 8) + 1 = 4 と一致します。理論値と実測が合いました。

4-4. 境界条件を1つ壊して、何が起きるか見る

同じ配列で、たった1か所だけ書き換えた2つの「壊れた版」を実行しました。

まず見てほしいのは、25・44・63・79 は3つの版すべてで正しく動いていることです。もしこの4つだけをテストしていたら、2種類のバグをどちらも見逃します。しかも等号落ちのほうはエラーも出さず、静かに「見つかりません」と答える。プログラムが動いていることは、正しいことの証明になりません。

もう一点。等号落ちで取りこぼされた 12・38・57・86 は、いずれも探索範囲が1件になった状態で見つかるはずだった値です。失敗は「境目」に集中する。だからテストは境目を狙って作ります（第54講の境界値分割）。

4-5. データ数を変えると伸び方が違う

要素数を変えて、最大比較回数を実測しました。

n が10倍になるたび、線形は10倍に増えるのに、二分は3〜4しか増えません。 これが「データが増えても時間がそれほど増えない」の正体です。100万件で20回という結論も、ここで確認できました。参考までに実時間も測ったところ、100万件の昇順リストで末尾の要素を200回探すと、先頭から順に探す方法が約1.09秒、二分探索を使う標準ライブラリ（bisect）が約0.00005秒。環境で変動する値ですが、桁が4つ違うという事実は変わりません。

5. 共通テストではこう出る（重要度A）

まず知っておいてほしい事実があります。大学入試センターが公表した「令和7年度大学入学共通テスト 試作問題『情報』の概要」の第5節「共通テスト用プログラム表記の例示」で、唯一の完全なサンプルプログラムとして選ばれているのが二分探索です。流れ図・Python3・JavaScript・VBA・Scratch の5通りとの対比まで、すべて二分探索で示されています。文法の見本として国がこのアルゴリズムを選んだ。 優先度を判断する材料としては、これで十分だと私は考えています。

出題の3つの型

落とし穴

• 前提の確認を飛ばす。 二分探索は昇順（または降順）に並んでいることが前提。問題文が整列済みと述べているかを読む
• 比較回数の数え方が問題ごとに違う。 「中央と比較した回数」か「ループを回った回数」か。定義は必ず問題文にあります
• 添字と「何番目」の混同。 添字が0から始まるなら、5番目の要素は Data[4]
• 見つからない場合を忘れる。 存在しない値のほうが比較回数が多くなることがあります（4-1で確認）
• 整数除算。 共通テスト用プログラム表記では商が ÷、余りが ％。普通の割り算の / とは別物です
• 降順の配列。 昇順で覚えた「小さければ右へ」がそのまま逆になります。丸暗記していると全滅します

練習用の自作問題（本記事オリジナル）

プログラム問題全体の解き方、時間配分、選択肢代入法については第54講「プログラムのトレース」にまとめました。

6. 情報Ⅱではこうなる

6-1. 探索の2つの型が、そのまま分類の2つの型になる

学習指導要領解説 情報編の情報Ⅱ(3)「情報とデータサイエンス」には、こう書かれています。

近傍法と木構造。 この2語を見た瞬間に、本講の2つの探索を思い出してほしいのです。

文部科学省の「情報Ⅱ」教員研修用教材は、k-近傍法を次のように定義しています。

「最も距離が近いk個」を知るには、原則としてすべての訓練データとの距離を計算します。これは線形探索です。 一方、同じ教材が扱う決定木は「訓練データを複数の属性を基に分割し，予測に活用する」もの。条件で枝を落として候補を絞るので、二分探索の構造です。

情報Ⅰで「全部見る」と「半分捨てる」の2つを学び、情報Ⅱで同じ2つが「全データと比べる」と「条件で分割する」として再登場する。扱う対象が配列から訓練データに変わっただけで、考え方は同じです。

6-2. 情報Ⅱでは「速さ」が精度とのトレードオフになる

同じ教材は、k-近傍法の正答率を上げる方法をこう結んでいます。

件数を増やせば正答率は上がります。ですが、1件を予測するのに必要な距離計算の回数も、件数に比例して増えます。 情報Ⅰでは「速いほうを選ぶ」で済んだ判断が、情報Ⅱでは「どこまで精度を取り、どこまで待てるか」という設計の問題になる。ここが接続点です。

正直に書いておくと、教材が書いているのは「件数を増やせば正答率が上がる」までで、そこから先は私の説明です。ただ、本講で「二分探索は整列というコストを前借りしている」と理解した人には見えるはずです。機械学習も、モデルを作るコストを先に払うから予測が速い。 前払いか後払いかという同じ話が、規模を変えて繰り返されます。

6-3. その先で待っているもの（データベースのインデックス）

「並べておけば速く探せる。ただし並べるコストがかかる」という本講の構図は、実務ではデータベースのインデックス（索引）として現れます。情報処理推進機構（IPA）の基本情報技術者試験シラバスには独立項目があります。

B-tree の tree は木。「半分ずつ絞る」構造を一般化したものです。そして用語例の先頭に「インデックス数，負荷」が置かれているのを見てください。インデックスは無料ではありません。作るのにも、データが更新されるたびに保つのにも負荷がかかる。3-2で見た「整列のコスト」と同じ話が、実務の語彙で書かれているだけです。

ひとつ断っておきます。文部科学省の「情報Ⅱ」教員研修用教材の関係データベースの節には、「インデックス」「索引」という語は出てきません（私が全文検索で確認しました）。ここは情報Ⅱの範囲そのものではなく、その先にある景色です。 情報Ⅱの関係データベースとSQLの扱いについては第43講「論理演算」に書きました。

6-4. 情報Ⅰと情報Ⅱの扱いの違い

最後に、混同しやすい点をひとつ。情報Ⅱ(4)「情報システムとプログラミング」の解説にも「効率」という語が何度も出てきますが、そちらの「効率」は実行時間ではなく開発の効率です。 原文は「開発の効率や運用の利便性などに配慮して設計する」「どのような関数を利用すれば効率的な開発ができるか判断する力」。実行の速さの話は(3)のデータサイエンス側にあります。同じ言葉が別の意味で使われているので、原文に当たって区別してください。 情報システムの設計と分割については第68講「プロトコルとTCP/IPの4階層」でも触れています。

まとめ

• 二分探索が速いのは1回で候補を半分捨てられるから。最大比較回数は floor(log₂ n) + 1 で、100万件なら20回（2¹⁹ < 10⁶ < 2²⁰）
• その速さは「昇順に並んでいる」という前提を借りている。整列のコストを勘定に入れなければ判断できない
• 1回しか探さないなら線形探索が勝つ。逆転はだいたい n/2 回あたり（n=1,000 なら505回以上）
• 境界条件を1つ間違えると、黙って取りこぼす（等号落ち）か、止まらなくなる（+1落ち）。しかも一部の値では正しく動くので気づけない
• 共通テスト用プログラム表記の唯一の完全な例示が二分探索。文法の見本として国が選んだアルゴリズム
• 情報Ⅱでは同じ2つの型が k-近傍法と木構造として再登場し、判断は「精度と処理量のつり合い」になる

出典（すべて2026年8月3日に取得）

• 文部科学省「高等学校学習指導要領（平成30年告示）解説 情報編」平成30年7月
• 文部科学省「高等学校情報科『情報Ⅰ』教員研修用教材」第3章 コンピュータとプログラミング（令和2年）
• 文部科学省「高等学校情報科『情報Ⅱ』教員研修用教材」第3章 情報とデータサイエンス 後半（令和2年6月）
• 大学入試センター「令和7年度大学入学共通テスト 試作問題『情報』の概要」（2022年11月9日公表）
• 情報処理推進機構（IPA）「基本情報技術者試験（レベル2）シラバス Ver.9.2」（2026年1月8日掲載）

本文に載せた比較回数・最大回数・整列コスト・損益分岐点・境界条件を壊したときの挙動は、すべて私がPythonで実行して確認した値です。共通テストの問題文・選択肢・図表・プログラムは転載していません。制度に関する記述は2026年8月時点のものです。

本書の全120講の一覧は『藤原進之介の最強120講義』の目次から、公開済みの講は情報Ⅰ 最強120講義カテゴリからご覧いただけます。