プログラミングにおいて、データの中から目的の値を見つける「探索アルゴリズム」は非常に重要です。その中でも**線形探索（リニアサーチ）と2分探索（バイナリサーチ）**は、最も基本的かつ実用的な探索手法として知られています。

本記事では、これら2つの探索アルゴリズムの違いや特徴、どちらを使うべきかの判断基準まで、初心者にもわかりやすく解説します。

テックジム東京本校では、情報科目の受験対策指導もご用意しております。

線形探索（Linear Search）とは

線形探索の基本概念

線形探索は、データの先頭から順番に1つずつ確認していき、目的の値を見つける最もシンプルな探索方法です。人間が本棚の本を1冊ずつ確認するような、直感的でわかりやすいアルゴリズムです。

線形探索の仕組み

def linear_search(arr, target):
    """線形探索の実装例"""
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 見つかった位置を返す
    return -1  # 見つからなかった場合

線形探索の特徴

メリット：

• 実装が簡単でわかりやすい
• データが並び替えられていなくても使える
• 小規模なデータセットでは効率的
• あらゆるデータ構造に適用可能

デメリット：

• データ量が多いと処理速度が遅くなる
• 最悪の場合、すべてのデータを確認する必要がある

計算量（時間複雑度）

• 最良の場合: O(1) – 最初の要素が目的の値
• 平均的な場合: O(n/2) ≈ O(n)
• 最悪の場合: O(n) – 最後の要素または存在しない

2分探索（Binary Search）とは

2分探索の基本概念

2分探索は、ソート済みのデータに対して使用できる高速な探索方法です。データの中央値と目的の値を比較し、探索範囲を半分ずつ絞り込んでいきます。辞書で単語を探すときに、真ん中あたりを開いて前後どちらかを判断する方法に似ています。

2分探索の仕組み

def binary_search(arr, target):
    """2分探索の実装例（反復版）"""
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid  # 見つかった位置を返す
        elif arr[mid] < target:
            left = mid + 1  # 右半分を探索
        else:
            right = mid - 1  # 左半分を探索
    
    return -1  # 見つからなかった場合

2分探索の特徴

メリット：

• 大量のデータでも非常に高速
• 探索範囲が半分ずつ減るため効率的
• 予測可能な性能

デメリット：

• データが事前にソート（並び替え）されている必要がある
• 実装が線形探索より複雑
• ランダムアクセスが可能なデータ構造が必要

計算量（時間複雑度）

• 最良の場合: O(1) – 中央の要素が目的の値
• 平均的な場合: O(log n)
• 最悪の場合: O(log n)

線形探索と2分探索の比較表

項目	線形探索	2分探索
時間計算量	O(n)	O(log n)
前提条件	なし	ソート済みデータが必要
実装難易度	簡単	やや複雑
適したデータ量	小〜中規模	中〜大規模
最悪時の比較回数（1000件）	1000回	約10回
最悪時の比較回数（100万件）	100万回	約20回

速度の違いを具体例で理解する

データ量別のパフォーマンス比較

100件のデータの場合：

• 線形探索：最大100回の比較
• 2分探索：最大7回の比較（約14倍高速）

10,000件のデータの場合：

• 線形探索：最大10,000回の比較
• 2分探索：最大14回の比較（約700倍高速）

100万件のデータの場合：

• 線形探索：最大100万回の比較
• 2分探索：最大20回の比較（約5万倍高速）

このように、データ量が増えるほど2分探索の優位性が顕著になります。

どちらを使うべき？使い分けのポイント

線形探索を使うべき場合

1. データ量が少ない（数十件程度）
2. データがソートされていない、またはソートのコストが高い
3. 1回だけの探索で、ソートする意味がない
4. 実装のシンプルさを優先したい
5. リンクリストなどランダムアクセスができないデータ構造

2分探索を使うべき場合

1. データ量が多い（数百件以上）
2. データが既にソート済み、または維持されている
3. 繰り返し探索を行う場合
4. パフォーマンスが重要な場面
5. 配列などランダムアクセス可能なデータ構造

判断フローチャート

データはソート済み？
├─ YES → データ量は多い？
│         ├─ YES → 2分探索を使用
│         └─ NO → どちらでも可（線形探索で十分）
└─ NO → ソートのコストは許容できる？
          ├─ YES → ソート後、2分探索を使用
          └─ NO → 線形探索を使用

実際のプログラミング言語での実装例

Python

# 線形探索
def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

# 2分探索
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 使用例
data = [1, 3, 5, 7, 9, 11, 13, 15]
print(linear_search(data, 7))   # 出力: 3
print(binary_search(data, 7))   # 出力: 3

JavaScript

// 線形探索
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}

// 2分探索
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

Java

// 線形探索
public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

// 2分探索
public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

実用例とユースケース

線形探索の実用例

• ユーザー入力の検証（少数の選択肢から選ぶ）
• 設定ファイルからの値の取得
• 小規模なマスターデータの検索
• リンクリストでの要素検索
• 未ソートのログファイルからの情報抽出

2分探索の実用例

• 大規模データベースのインデックス検索
• 辞書や電話帳の検索
• ゲームのスコアランキング検索
• バージョン管理システム（git bisectなど）
• 数値計算における解の探索

よくある間違いと注意点

線形探索での注意点

1. 早期リターンを忘れずに実装する
2. 見つからなかった場合の処理を明確にする
3. インデックス範囲外アクセスに注意

2分探索での注意点

1. データが必ずソート済みであることを確認
2. オーバーフローに注意（mid計算時）
3. 境界条件（left, right）の扱いに注意
4. 同じ値が複数ある場合の動作を理解する

パフォーマンスチューニングのヒント

線形探索の最適化

# よく検索される値を配列の前方に配置
# キャッシュの活用
# 複数の値を同時に探索する場合は1回のループで処理

2分探索の最適化

# データの事前ソートを1回だけ行う
# ソート済みデータの維持（挿入ソートなど）
# 標準ライブラリの活用（Python: bisect, Java: Arrays.binarySearch）

まとめ

線形探索と2分探索は、それぞれ異なる場面で最適な探索アルゴリズムです。

線形探索は実装が簡単で、小規模データやソートされていないデータに適しています。一方、2分探索はソート済みデータに対して圧倒的な速度を発揮し、大規模データの探索に最適です。

重要なのは、データの特性と要件に応じて適切なアルゴリズムを選択することです。データ量、ソート状態、探索頻度などを考慮し、最適な手法を選びましょう。

選択の基準（再掲）

• データ量が少ない or ソート不可 → 線形探索
• データ量が多い and ソート済み → 2分探索
• 迷った場合 → まず線形探索で実装し、パフォーマンスが問題になったら2分探索へ移行

プログラミングの基礎として、両方のアルゴリズムをしっかり理解し、状況に応じて使い分けられるようになりましょう。

参考資料

• アルゴリズムの計算量について理解を深めたい方は「ビッグO記法」を学習すると良いでしょう
• 実際のプログラミング言語では、標準ライブラリに探索機能が用意されていることが多いため、積極的に活用しましょう
• さらに高度な探索手法として、ハッシュテーブル（O(1)）やバランス木（O(log n)）なども学習すると視野が広がります

■らくらくPython塾 – 読むだけでマスター

【現役エンジニア歓迎】プログラミング学習お悩み相談会

【現役エンジニア歓迎】プログラミング学習お悩み相談会

【情報I】受験対策・お悩み相談会（オンライン・無料）

【情報I】受験対策・お悩み相談会（オンライン・無料）

【オンライン無料】ゼロから始めるPython爆速講座

【無料・オンライン】ゼロからはじめるPython爆速講座

■テックジム東京本校

格安のプログラミングスクールといえば「テックジム」。
講義動画なし、教科書なし。「進捗管理とコーチング」で効率学習。
対面型でより早くスキル獲得、月額2万円のプログラミングスクールです。
情報科目の受験対策指導もご用意しております。

テックジム東京本校｜「情報」科目受験生歓迎