ゆめさくエンジニア研究所女性向けエンジニアスクール女性向けエンジニアスクール
ログイン

線形探索と二分探索

回 2-1　道 2 データ構造とアルゴリズム

二分探索は、小さい順に並んだデータの真ん中を見て、探す値がどちら側にあるかで候補を半分ずつ捨てていく探し方です。端から 1 つずつ比べる線形探索は 100 万件で最悪 100 万回比べますが、二分探索は真ん中を見る回数が最悪でも 20 回で済みます。データが並んでいることが前提で、並んでいないと見落とします。

目安 50 分2-1 (2-0〜2-10 の中)

読み終えたらデータが 1,000 倍になっても、二分探索で真ん中を見る回数が 10 回しか増えない理由を説明できる

この頁の流れ

  1. 1100 万件の名簿から 1 人を、何回で見つけられるか
  2. 2線形探索と二分探索はどう動くのか
  3. 3動かして確かめる
  4. 4二分探索はどこで崩れるのか
  5. 5二分探索は仕事でどう確かめるのか
  6. 6関わる実例
  7. 7よくある問い
  8. 8確認クイズ
  9. 9説明課題
  10. 10もっと深く
  11. 11一次資料
  12. 12次へ

探す前にデータが並んでいるかを確かめ、端から比べるか、真ん中から半分ずつ捨てるかを選べるようになります。

文 ゆめさくコード編集部公開 2026年10月26日更新 2026年10月26日出典を確かめた日 2026年10月26日

100 万件の名簿から 1 人を、何回で見つけられるか

名簿が番号順に並んでいれば、100 万件からでも、真ん中を見る回数は最悪 20 回で 1 人を見つけられます。端から 1 件ずつ見ると、最悪で 100 万回です。

1 から 100 の数を当てる遊びを思い出してください。相手が「もっと大きい」「もっと小さい」と答えてくれるなら、1 から順に言うより、まず 50 と言うのが得です。外れても、残りの候補が半分に減るからです。

この「真ん中を見て半分を捨てる」探し方が二分探索 (にぶんたんさく) です。端から順に見る探し方は線形探索 (せんけいたんさく) と呼びます。

この回では、2 つの探し方で値を見た回数を実際に数え、二分探索がなぜ速いのか、どこで使えなくなるのかを確かめます。

番号順に並んだ 7 冊から、真ん中を見て片方を捨て、2 回で 6 を見つける図

線形探索と二分探索はどう動くのか

線形探索は端から 1 つずつ比べ、二分探索は並んだデータの真ん中を見て候補を半分ずつ捨てます。違いは、データが並んでいることを使うかどうかです。

線形探索は端から順に比べる

線形探索は、先頭から 1 つずつ「探す値と同じか」を比べ、見つかったら止まります。データの並び順は問いません。

最悪なのは、探す値がいちばん後ろにあるときと、どこにも無いときです。どちらも全部と比べるので、n 件なら n 回比べます。計算量 (データが増えたときの手間の増え方) は O(n) です。

5 冊を端から見ていき、見つかった所で止まり、無いときは最後まで見る図

二分探索は真ん中を見て半分を捨てる

二分探索は、小さい順に並んだデータで、次の手順をくり返します。

  1. 候補の範囲の真ん中の値を見る
  2. 探す値と同じなら、見つかったので止まる
  3. 真ん中の値が探す値より小さければ、真ん中とその左を捨てる。大きければ、真ん中とその右を捨てる
  4. 候補が無くなったら、探す値は無い

1 回見るたびに、候補はほぼ半分になります。1000 件なら、500、250、125 と減り、10 回ほどで 1 件まで絞れます。

この頁では、二分探索の手間を「真ん中の値を見た回数」で数えます。1 回見るたびに「同じか」と「小さいか」の 2 つを比べますが、数えるのは見た回数です。線形探索は「比べた回数」で数えます。

二分探索の絞り込み

1,000 倍で 10 回しか増えない理由

2 を 10 回掛けると 1024 で、1000 を少し超えます。ですから、1 回で半分にする操作を 10 回くり返すと、1000 件の候補が 1 件まで絞れます。

データが 1,000 倍の 100 万件になっても、2 を 20 回掛けると 1048576 で、100 万を超えます。1,000 倍は 2 を約 10 回掛けた数なので、見る回数は 10 回増えるだけです。

これを計算量で書くと O(log n) です。log2 n は「2 を何回掛けると n になるか」を表します。

件数線形探索二分探索
1,0001,00010
10,00010,00014
100,000100,00017
1,000,0001,000,00020

表は、いちばん後ろの値を探したときの回数で、線形探索は比べた回数、二分探索は真ん中を見た回数です。数は下の 1 本目のコードの出力そのものです。

動かして確かめる

1 本目は、件数を 1,000 から 1,000,000 まで変えて、いちばん後ろの値を探します。出力は左から、件数、線形探索で比べた回数、二分探索で真ん中を見た回数です。

動かす 線形探索と二分探索の回数を数える

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

1000 1000 10
10000 10000 14
100000 100000 17
1000000 1000000 20

線形探索の回数は件数と同じで、100 万件なら 100 万回です。二分探索は 10、14、17、20 回です。1,000 件から 1,000,000 件へ 1,000 倍になって、見た回数は 10 回から 20 回へ、10 回増えただけです。

2 本目は、1 から 100 の数当てを二分探索で行い、100 通りの答えすべてで見た回数を数えます。後半は、件数 n ごとに、最悪の回数と、n を 2 進数で書いたときの桁数を並べます。出力は左から、n、n の 2 進数、ある値を探したときの最悪、無い値を探したときの最悪、n.bit_length() (2 進数の桁数) です。

動かす 数当てと 2 進数の桁数

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

最悪 7
平均 5.8
1 回で当たる 1
7 回かかる 37
8 1000 4 4 4
100 1100100 7 7 7
1000 1111101000 10 10 10
1024 10000000000 11 11 11

1 から 100 の数当ては、最悪でも 7 回で当たり、100 通りの平均は 5.8 回です。1 回で当たるのは真ん中の 1 通りだけで、7 回かかるのは 37 通りです。

後半の出力では、最悪の回数が、ある値でも無い値でも、n の 2 進数の桁数と同じです。1000 は 2 進数で 10 桁なので最悪 10 回、1024 は 11 桁なので最悪 11 回です。道 1 で学んだ 2 進数の桁数が、そのまま二分探索の最悪の回数になります。

二分探索はどこで崩れるのか

二分探索は、データが並んでいること、真ん中の位置を正しく計算できること、並べる手間に見合うだけ探すこと、の 3 つが前提です。どれかが崩れると、見落とすか、落ちるか、かえって遅くなります。

並んでいないと、ある値を見落とす

二分探索は「探す値が真ん中の値より大きいなら、真ん中より左には無い」と決めつけて捨てます。並んでいないデータでは、この決めつけが外れます。

動かす 並んでいないと見落とす

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

in で探す True
並べずに二分探索
 見た 1
 見た 7
 見た 5
答え False
並べてから二分探索
 見た 5
 見た 7
 見た 9
答え True

[3, 9, 1, 7, 5] には 9 がありますが、並べずに二分探索すると、1、7、5 を見て「無い」と答えます。最初に 1 を見て、9 は 1 より大きいので左を捨てた時点で、左にある 9 を見落としています。並べてから探すと、5、7、9 と見て見つかります。

並んでいないデータに二分探索を使っても、エラーは出ません。間違った答えが静かに返るので、気づきにくい失敗です。

真ん中の計算が、器の幅を超える

真ん中の位置を (low + high) // 2 で求める書き方は、整数の器の幅が決まっている言語では、low + high が器を超えると壊れます。Java の int は 32 ビットで、2147483647 (2 の 31 乗 − 1) までしか入りません。

Python の int は器の幅が決まっていないので、32 ビットの器に入れたときの値を & 0xFFFFFFFF で作って確かめます。

動かす 32 ビットで真ん中を求める

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

本当の和 3100000000
32 ビットの和 -1194967296
誤った真ん中 -597483648
正しい真ん中 1550000000

本当の和は 3100000000 ですが、32 ビットの器では −1194967296 になり、真ん中は −597483648 という負の位置になります。配列に負の位置はないので、Java では例外が出て処理が止まります。low + (high - low) // 2 と書けば、足す前に差を取るので器を超えず、正しい真ん中の 1550000000 が出ます。

1 回しか探さないなら、並べるほうが損

二分探索の前には、データを並べる手間がかかります。1 回か 2 回しか探さないなら、並べずに線形探索するほうが、比べる回数の合計は少なくなります。

次のコードは、1000 件のばらばらの数を、マージソート (次の次の回 2-3 で学ぶ速い並べ方) で並べたときに比べた回数を数えます。そのあと 1000 件すべてを 1 回ずつ探し、1 回あたりの平均の回数を出します。ここでは並べる手間と足し合わせるので、二分探索も、真ん中を見るたびに == と < で比べた回数を数えます。最後に、何回探せば「並べて二分探索」の合計が「線形探索」の合計より少なくなるかを数えます。並びは、乱数の代わりに決まった式で混ぜているので、誰が動かしても同じになります。

動かす 並べてから探すと得になる回数

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

並べる 8723
線形の平均 500.5
二分の平均 16.974
得になる探す回数 19

並べるのに 8723 回比べました。1 回探すあたりの平均の比べた回数は、線形探索が 500.5 回、二分探索が 16.974 回です。探す回数が 19 回になったところで、並べる手間を含めても二分探索のほうが少なくなります。18 回までなら、並べずに端から探すほうが少ない回数で済みます。

データが少ないときや、探すのが 1 回きりのときは、線形探索で十分です。何度も探すと分かっているデータは、先に 1 回並べておく価値があります。

二分探索は仕事でどう確かめるのか

仕事では、自分で二分探索を書くより、言語に入っている道具を使い、並んでいることと境目の値を試験で確かめます。

  1. Python では標準の bisect を使う。bisect_left(a, x) は、並んだ a に x を入れても並びが崩れない、いちばん左の位置を返す。公式文書は、並んだ状態を保つための道具で、比べるのが重い長いリストでは線形探索や並べ直しより得になることがあると書いている
  2. 探す前に、データが並んでいることを確かめる。試験で a == sorted(a) を見るのが手軽
  3. 線形探索と答えを照らす。どの値を探しても、二分探索と線形探索が同じ答えを返すことを試験で確かめる
  4. 境目を試す。0 件、1 件、先頭、末尾、無い値、同じ値が並んだ所の 6 つは、書き間違いが出やすい

二分探索は、値を探すだけでなく、条件が切り替わる境目を探すのにも使えます。Git の git bisect は、公式文書によると、二分探索でバグが入ったコミットを探す道具です。バグのあるコミットと、バグが入る前のコミットを 1 つずつ教えると、その間のコミットを選んで良いか悪いかを尋ね、答えるたびに候補を絞ります。

データベースの索引も、並びを使って探します。PostgreSQL の公式文書は、B-tree の索引は並べられるデータの「等しい」と「範囲」の問い合わせを扱え、< や >= を使う比べで使われると書いています。

bisect で探す

from bisect import bisect_left

def find(a, x):
    i = bisect_left(a, x)
    if i == len(a):
        return False
    return a[i] == x

関わる実例

Java の二分探索に 9 年ほど潜んでいた上限越え (2006年6月2日)

2006年6月2日、Google の Joshua Bloch は公式ブログで、自分が JDK の java.util.Arrays に書いた二分探索に、真ん中の計算のバグがあったと公表しました。バグは int mid = (low + high) / 2; の 1 行で、low と high の和が int の最大値 (2 の 31 乗 − 1) を超えると負の数になり、Java では ArrayIndexOutOfBoundsException が出ます。

記事によると、このバグは要素の数が 2 の 30 乗 (約 10 億) 以上の配列で表に出ます。本に載って証明まで付いた二分探索にも同じ誤りがあり、JDK の版では 9 年ほど潜んだあと、誰かのプログラムを壊して報告されました。直し方として low + ((high - low) / 2) と、符号なしで右にずらす (low + high) >>> 1 が示されています。

崩れた前提は「真ん中の位置は、足して 2 で割れば求まる」です。数の値は正しくても、それを入れる器の幅が足りませんでした。上の「32 ビットで真ん中を求める」のコードで見た負の真ん中が、本当に起きた例です。記事は、同じ誤りがマージソートなど、分けて解く手順にも当てはまると書いています。

出典は Nearly All Binary Searches and Mergesorts are Broken (Google Research Blog) です。

よくある問い

二分探索の計算量はなぜ O(log n) なのですか

1 回見るたびに候補が半分になるので、n 件を 1 件まで絞るのに、2 を何回掛けると n になるかの回数だけ見れば済むからです。この回数が log2 n です。上の出力の通り、最悪の回数は n を 2 進数で書いたときの桁数と同じで、1000 件なら 10 回です。

二分探索は並んでいないデータにも使えますか

使えません。上のコードの通り、並んでいないデータでは、ある値でも「無い」と答えることがあり、エラーも出ません。何度も探すなら先に並べてから使い、1 回だけなら線形探索を使います。

二分探索とハッシュ探索はどう使い分けますか

ある値がちょうどあるかを調べるだけなら、ハッシュ探索 (鍵から置き場を計算して直接見る探し方) が速く、Python の set や dict の in は公式文書で平均 O(1) とされています。二分探索は、並びを使えるので、「30 以上 50 未満」のような範囲や、「x 以上でいちばん小さい値」を探すときに向いています。

同じ値が並んでいるとき、最初の位置は探せますか

探せます。Python の bisect_left は、同じ値があるときはそのいちばん左の位置を返し、bisect_right はいちばん右の次の位置を返します。2 つの差を取ると、その値がいくつあるかも分かります。

二分探索は配列のほかにも使えますか

使えます。「ある所を境に、条件が偽から真に切り替わる」ものなら、その境目を二分探索で探せます。バグの入ったコミットを探す git bisect や、条件を満たす最小の値を探す問題がその例です。

確認クイズ

答えだと思う選択肢を押すと、その場で正誤と理由が開きます。4 問すべてに正しく答えると、この回は修了で、石が緑に変わります (この端末のブラウザに残ります)。間違えた問いは、あとから解き直せます。

1 問目

100 万件の並んだデータから二分探索で探すとき、真ん中を見る回数は最悪で何回ですか。

2 問目

並んでいないリスト [3, 9, 1, 7, 5] で、二分探索を使って 9 を探しました。何が起きますか。

3 問目

1000 件のばらばらのデータから、値を 1 回だけ探します。比べる回数の合計がいちばん少ないのはどれですか。

4 問目

このコードを動かすと何が出ますか。count は、二分探索で真ん中を見た回数を返します。a は 1 から 15 までの並んだリストです。

真ん中を見た回数

def count(a, x):
    lo = 0
    hi = len(a) - 1
    n = 0  # 真ん中を見た回数
    while lo <= hi:
        mid = (lo + hi) // 2
        n += 1
        if a[mid] == x:
            return n
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return n


a = list(range(1, 16))
print(count(a, 1))

説明課題

データが 1,000 件から 1,000,000 件へ 1,000 倍になっても、二分探索で真ん中を見る回数が 10 回しか増えない理由を、「半分」と「2 の 10 乗」という言葉を使って、3 文以内で説明してください。書いたら、下の模範解答を開いて比べてください。

模範解答

自分の説明を書いてから開いて、比べてください。

この回の先の一歩

並んだデータから探す処理は、データベースの索引や git bisect のように、仕事の道具の中で毎日動いています。いまの自分が転職までの道のどの段にいるかは、転職診断で確かめられます。

もっと深く

この回の続きを、ゆめさくのコースの章や道具で深められます。頁の中の確認クイズに答えたあと、手を動かす量を増やしたいときに使ってください。

一次資料

どれも 2026年10月26日に開いて、題と中身を確かめました。

次へ

前の回 2-0アルゴリズムとは順次、分岐、反復の 3 つで書く手順次の回 2-2バブルソートと挿入・選択ソート遅いソート 3 つ、2 倍で約 4 倍

道 2 データ構造とアルゴリズムの回

  1. 2-0アルゴリズムとは順次、分岐、反復の 3 つで書く手順頁で読む
  2. 2-1線形探索と二分探索100 万件でも 20 回で見つかるこの回
  3. 2-2バブルソートと挿入・選択ソート遅いソート 3 つ、2 倍で約 4 倍頁で読む
  4. 2-3クイックソートとマージソート速いソート 2 つ、平均と最悪頁で読む
  5. 2-4スタックとキュー積む順と並ぶ順頁で読む
  6. 2-5再帰自分を呼んで小さくする頁で読む
  7. 2-6木と二分探索木たどる順、片寄り頁で読む
  8. 2-7ハッシュテーブル鍵から一気に引く、衝突頁で読む
  9. 2-8ダイクストラ法と最短経路点と線、幅優先、重みのある道頁で読む
  10. 2-9動的計画法同じ計算を 2 度しない頁で読む
  11. 2-10試験と面接で確かめる基本情報 科目B、道場 10 問、面接 20 問頁で読む

道 2 の頁へ戻るほかの道を見る