Zenn
🤖

【C#アルゴリズム】二分探索

2024/12/01に公開
C#
アルゴリズム
二分探索
tech

はじめに

paiza　で二分探索を用いる問題が出てきたのでそれについてまとめます。

二分探索（二部探索）とは

二分探索（binary search）は、整列されたデータから効率的に特定の値を探すアルゴリズムです。探索範囲を中央で分割しながら、範囲を半分に絞り込むことで高速に目的の値を見つけます。計算量は O(\log n) で、大規模データの探索に適しています。

基本原理

  1. 整列されたデータが前提:

    • データが昇順（または降順）に並んでいる必要があります。

  2. 中央の要素を基準に範囲を絞り込む:

    • 中央要素と探索対象（目標値）を比較します。
      • 等しい場合: 探索成功。
      • 目標値が小さい場合: 中央の左側を新たな探索範囲にする。
      • 目標値が大きい場合: 中央の右側を新たな探索範囲にする。

  3. 範囲が空になるまで繰り返す:

    • 見つかれば成功、見つからなければ探索失敗。

C#での実装例

二分探索（配列 A（昇順にソートされていることを前提）から、値 k が存在するかを確認する）

  1. 標準メソッドを使用する場合

    int[] A = { 3, 6, 7, 2, 5 };
Array.Sort(A);
int k = 2;
int index = Array.BinarySearch(A, k);
Console.WriteLine(index >= 0 ? "Yes" : "No"); // Yesが表示される

  2. メソッドを自作する場合

    // 二分探索を行う関数
// 配列 A（昇順にソートされていることを前提）から、値 k が存在するかを確認する。
// n は配列 A の長さ。
private static bool BinarySerch(int[] A, int n, int k)
{
    bool check = false; // 探索結果を格納（初期値は false）
    int left = 0; // 探索範囲の左端
    int right = n - 1; // 探索範囲の右端

    // 左端が右端を超えるまでループ（探索範囲が存在する限り繰り返す）
    while (left <= right)
    {
        // 探索範囲の中央を計算
        int mid = (left + right) / 2;

        // 配列の中央要素が目標値と一致した場合、探索成功
        if (A[mid] == k)
        {
            return true; // true を返して終了
        }
        // 中央要素が目標値より小さい場合、探索範囲を右側に絞り込む
        else if (A[mid] < k)
        {
            left = mid + 1;
        }
        // 中央要素が目標値より大きい場合、探索範囲を左側に絞り込む
        else
        {
            right = mid - 1;
        }
    }

    // 目標値が見つからない場合、false を返す
    return check;
}

応用例1: Lower Bound（昇順にソートされた配列 A の中で、k 以上となる最初の位置（インデックス）を返す。）

// LowerBound関数
// 昇順にソートされた配列 A の中で、k 以上となる最初の位置（インデックス）を返す。
// n は配列 A の要素数。
private static int LowerBound(int[] A, int n, int k)
{
    int left = 0; // 探索範囲の左端
    int right = n; // 探索範囲の右端（配列の範囲外を初期値にする）

    // 左端が右端と一致するまでループ（探索範囲が存在する限り繰り返す）
    while (left < right)
    {
        int mid = (left + right) / 2; // 探索範囲の中央を計算

        // 中央の要素が k より小さい場合、探索範囲を右側に絞り込む
        if (A[mid] < k)
        {
            left = mid + 1; // 探索範囲の左端を更新
        }
        // 中央の要素が k 以上の場合、探索範囲を左側に絞り込む
        else
        {
            right = mid; // 探索範囲の右端を更新
        }
    }

    // 探索終了時、right（または left）が k 以上となる最初のインデックス
    return right;
}

応用例2: Upper Bound（昇順にソートされた配列 A の中で、k を超える最初の位置（インデックス）を返す。）

// UpperBound関数
// 昇順にソートされた配列 A の中で、k を超える最初の位置（インデックス）を返す。
// n は配列 A の要素数。
private static int UpperBound(int[] A, int n, int k)
{
    int left = 0; // 探索範囲の左端
    int right = n; // 探索範囲の右端（配列の範囲外を初期値にする）

    // 左端が右端と一致するまでループ（探索範囲が存在する限り繰り返す）
    while (left < right)
    {
        int mid = (left + right) / 2; // 探索範囲の中央を計算

        // 中央の要素が k 以下の場合、探索範囲を右側に絞り込む
        if (A[mid] <= k)
        {
            left = mid + 1; // 探索範囲の左端を更新
        }
        // 中央の要素が k より大きい場合、探索範囲を左側に絞り込む
        else
        {
            right = mid; // 探索範囲の右端を更新
        }
    }

    // 探索終了時、right（または left）が k を超える最初のインデックス
    return right;
}

LowerBound vs UpperBound

こちらについては以下の記事でまとめました。
https://zenn.dev/student_blog/articles/9e70f265f774e8

応用例

  • 検索エンジンのインデックス探索:
    • 整列済みのデータから特定の単語やURLを高速に検索。
  • 図書館の蔵書検索:
    • 書籍の索引から特定のページ番号を探す。
  • IoTデータの探索:
    • センサーデータの中で、ある閾値以上・以下のデータを効率的に抽出。

なにせ、大規模なデータから必要な要素を取り出したい時に使えます。

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5

LowerBoundとUpperBoundに関する記事
https://zenn.dev/student_blog/articles/9e70f265f774e8

Discussion