C++による二分探索と線形探索の比較プログラム

コンピュータプログラミングにおいて、特定の要素を探すために二分探索と線形探索（シーケンシャル探索）の2つのアルゴリズムが広く用いられます。二分探索の計算量はO(log n)、線形探索はO(n)であり、データがソート済みであれば二分探索の方が高速です。

アルゴリズムの概要

二分探索

ソート済みの配列に対して、探索範囲を半分ずつ絞り込んでいく手法です。

BinarySearch(配列 arr, 要素数 n, 開始インデックス, 終了インデックス, 反復回数, 探索値)
  反復回数をインクリメント
  中央インデックス mid = start + (end - start + 1) / 2 を計算
  探索値が範囲外、または mid == end なら「見つからず」で終了
  探索値 == arr[mid] なら位置を返す
  探索値 == arr[start] または arr[end] なら位置を返す
  探索値 > arr[mid] なら後半部 (mid 〜 end) を再帰探索
  それ以外なら前半部 (start 〜 mid) を再帰探索

線形探索

配列の先頭から順に要素を比較していく最も単純な手法です。

LinearSearch(配列 arr, 要素数 n, 探索値)
  i = 0 から n-1 まで繰り返す
    反復回数を出力
    arr[i] == 探索値 なら位置と反復回数を返す
  見つからなければ「見つからず」を出力

実装例（C++）

#include <iostream>
using namespace std;

int BinarySearch(int a[], int start, int end, int item, int iter) {
    int mid;
    cout << "\niteration " << iter + 1;
    iter++;
    mid = start + (end - start + 1) / 2;
    
    if (item > a[end] || item < a[start] || mid == end) {
        cout << "\nNot found";
        return iter;
    } else if (item == a[mid]) {
        cout << "\n item found at " << mid << " index.";
        return iter;
    } else if (item == a[start]) {
        cout << "\n item found at " << start << " index.";
        return iter;
    } else if (item == a[end]) {
        cout << "\n item found at " << end << " index.";
        return iter;
    } else if (item > a[mid])
        return BinarySearch(a, mid, 9, item, iter);
    else
        return BinarySearch(a, start, mid, item, iter);
}

int LinearSearch(int a[], int n, int item) {
    for (int i = 0; i < n; i++) {
        cout << "\niteration " << i + 1;
        if (a[i] == item) {
            cout << "\n item found at " << i << " index.";
            return i + 1;
        }
    }
    cout << "\nNot found";
    return n;
}

int main() {
    int n, B, L;
    int a[10] = {2, 7, 14, 24, 26, 35, 38, 41, 49, 53};
    
    cout << "\nEnter the element to be searched: ";
    cin >> n;
    
    cout << "\n\n\t\t\tBinary Search :";
    B = BinarySearch(a, 0, 9, n, 0);
    
    cout << "\n\n\t\t\tLinear Search :";
    L = LinearSearch(a, 10, n);
    
    if (L > B)
        cout << "\n\nBinary search is better for this search.";
    else if (L < B)
        cout << "\n\nLinear search is better for this search.";
    else
        cout << "\n\nBoth are equally efficient for this search.";
    
    return 0;
}

実行結果の例

ケース1：探索値 7（先頭付近）

Enter the element to be searched: 7

			Binary Search :
iteration 1
iteration 2
iteration 3
iteration 4
item found at 1 index.

			Linear Search :
iteration 1
iteration 2
item found at 1 index.

Linear search is better for this search.

先頭付近の要素では線形探索の方が少ないステップで見つかります。

ケース2：探索値 53（末尾）

Enter the element to be searched: 53

			Binary Search :
iteration 1
item found at 9 index.

			Linear Search :
iteration 1
iteration 2
iteration 3
iteration 4
iteration 5
iteration 6
iteration 7
iteration 8
iteration 9
iteration 10
item found at 9 index.

Binary search is better for this search.

末尾の要素では二分探索が圧倒的に高速です。

ケース3：探索値 1（存在しない）

Enter the element to be searched: 1

			Binary Search :
iteration 1
Not found

			Linear Search :
iteration 1
iteration 2
iteration 3
iteration 4
iteration 5
iteration 6
iteration 7
iteration 8
iteration 9
iteration 10
Not found

Binary search is better for this search.

存在しない値でも二分探索は即座に範囲外と判定できます。

まとめ

• 二分探索：ソート済みデータに対して有効。最悪ケースでもO(log n)で安定して高速。
• 線形探索：ソート不要で実装が簡単。データ数が少ない、または探索対象が先頭付近にある場合に有利。
• 実用上はデータの状態とサイズに応じて使い分けるのが最適です。