【C#】List.BinarySearchでソート済みリストを高速に検索する方法

2025年11月15日

リストの検索とパフォーマンス

List<T>（ジェネリックリスト）に格納されたデータから特定の要素を探す際、Containsメソッド、IndexOfメソッド、またはLINQのFirstOrDefaultメソッドを使用するのが一般的です。

これらの方法は非常に直感的ですが、内部的には「線形探索（Linear Search）」を行っています。線形探索は、リストの先頭から[0], [1], [2]…と順番に、一致するものが見つかるまで（あるいは最後まで）チェックし続けます。

要素数が100個程度であれば問題ありませんが、リストの要素数が100万件あった場合、最悪の場合100万回の比較が必要となり、パフォーマンスが著しく低下します。

この問題を解決するのが List<T>.BinarySearch（二分探索）メソッドです。

`BinarySearch`（二分探索）とは

BinarySearch（二分探索）は、O(log n)という非常に高速なアルゴリズムで要素を検索します。

これは「辞書で単語を探す」方法に似ています。リスト全体（100万件）の真ん中を調べ、探している値がそれより「小さい」か「大きい」かに基づいて、検索対象を半分（50万件）に絞り込みます。次はその半分の真ん中を調べ…と、検索範囲を半分、半分に減らしていくため、100万件のデータでも約20回の比較で検索が完了します。

必須の前提条件：`Sort`（並べ替え）

BinarySearch（二分探索）が正しく動作するためには、絶対に守らなければならない前提条件があります。

それは、BinarySearchを呼び出す前に、List<T>が既に昇順（小さい順、または辞書順）にソート（並べ替え）されていることです。

もしソートされていないリストに対してBinarySearchを実行した場合、アルゴリズムが前提（整列されていること）に基づいて動作するため、エラーにはなりませんが、見つかるはずの要素が見つからない（負の数を返す）か、まったく無関係なインデックスを返すなど、予測不可能な誤った結果を返します。

正しい手順:

List<T>.Sort() を呼び出して、リストを昇順に並べ替える。
List<T>.BinarySearch(item) を呼び出す。

`BinarySearch` の戻り値の解釈

BinarySearchは、検索結果をint型で返しますが、その意味はIndexOfとは少し異なります。

index >= 0 (0または正の数): 検索に成功。戻り値は、見つかった要素のインデックスです。
index < 0 (負の数): 検索に失敗（要素は見つからなかった）。

コード例1：検索に成功する場合

stringのリストをSort()で並べ替えた後、BinarySearchで要素を検索する例です。

using System;
using System.Collections.Generic;

public class BinarySearchFoundExample
{
    public static void Main()
    {
        var productCodes = new List<string>
        {
            "P-005", "A-102", "Z-001", "K-050", "D-010"
        };

        Console.WriteLine("--- ソート前 ---");
        Console.WriteLine(string.Join(", ", productCodes));

        // 1. 必須：BinarySearch の前に必ずソートする
        productCodes.Sort(); // "A-102", "D-010", "K-050", "P-005", "Z-001"

        Console.WriteLine("\n--- ソート後 ---");
        Console.WriteLine(string.Join(", ", productCodes));

        // 2. 検索したいアイテム
        string target = "K-050";

        // 3. BinarySearch を実行
        int index = productCodes.BinarySearch(target);

        Console.WriteLine($"\n'{target}' を検索...");

        // 4. 結果を判定 (0以上か？)
        if (index >= 0)
        {
            Console.WriteLine($"結果: 見つかりました。");
            Console.WriteLine($"インデックス: {index} (値: {productCodes[index]})");
        }
        else
        {
            Console.WriteLine($"結果: 見つかりませんでした。");
        }
    }
}

出力結果:

--- ソート前 ---
P-005, A-102, Z-001, K-050, D-010

--- ソート後 ---
A-102, D-010, K-050, P-005, Z-001

'K-050' を検索...
結果: 見つかりました。
インデックス: 2 (値: K-050)

コード例2：検索に失敗した場合（負の数の意味）

BinarySearchがindex < 0（負の数）を返した場合、その数値は単なる「エラー」ではなく、**「もしその要素を挿入するならば、リストのソート順を維持するために、どのインデックスに挿入すべきか」**という情報を含んでいます。

戻り値（負の数）は、**次に大きい要素のインデックスの「ビットごとの補数（~）」**です。

~（ビットごとの補数）演算子を使って負の値を反転させることで、この「挿入すべきインデックス」を取り出すことができます。

using System;
using System.Collections.Generic;

public class BinarySearchNotFoundExample
{
    public static void Main()
    {
        // ソート済みのリスト
        var sortedScores = new List<int> { 10, 20, 40, 50 };

        int target = 30; // 20 と 40 の間に挿入されるべき値

        // 1. 30 を検索 (存在しない)
        int index = sortedScores.BinarySearch(target);

        Console.WriteLine($"リスト: {string.Join(", ", sortedScores)}");
        Console.WriteLine($"'{target}' を検索...");
        Console.WriteLine($"戻り値: {index} (負の数)");

        if (index < 0)
        {
            // 2. 戻り値 (負の数) のビットごとの補数を計算
            // ~index で「次に大きい要素(40)のインデックス」がわかる
            int insertionPoint = ~index; 

            Console.WriteLine("結果: 見つかりませんでした。");
            Console.WriteLine($"挿入すべきインデックス: {insertionPoint}"); // 2
        }
    }
}

出力結果:

リスト: 10, 20, 40, 50
'30' を検索...
戻り値: -3 (負の数)
結果: 見つかりませんでした。
挿入すべきインデックス: 2

30は40（インデックス 2）の直前に挿入すべきであるため、~2（ビットごとの補数 2）である-3が返され、~(-3)によって正しい挿入位置2が復元されています。

まとめ

List<T>.BinarySearchは、大量のデータが含まれるリストから要素を高速（O(log n)）に検索するための強力なメソッドです。

必須条件: 呼び出す前にList<T>.Sort()でリストを昇順にソートしておく必要があります。
戻り値（成功）: 0以上のインデックス。
戻り値（失敗）: 0未満の負の数。この負の値を ~（ビットごとの補数）演算子にかけると、ソート順を維持するためにその要素を挿入すべきインデックスがわかります。