C# BinarySearch와 검색 알고리즘 성능 비교

이 글은 C#에서 Array.BinarySearch, List<T>.BinarySearch 사용법과 선형 검색(Linear Search) 대비 성능 차이를 간략히 정리합니다. 정렬 여부, 비교자 일관성, 데이터 크기에 따른 선택 기준을 함께 제시합니다.

1. BinarySearch 개요

BinarySearch는 정렬된 컬렉션에서 O(log n)으로 대상을 찾는 알고리즘입니다. 선형 검색은 O(n)으로 단순하지만 데이터가 커질수록 비용이 빠르게 증가합니다. BinarySearch는 반드시 같은 기준으로 정렬이 되어 있어야 하며, 찾는 값과 정렬 기준(Comparer)이 일관되어야 합니다.

2. 기본 사용법 (배열/리스트)

// 배열에서 BinarySearch
int[] data = { 1, 3, 5, 7, 9 };
int idx = Array.BinarySearch(data, 7); // 3

int idxMissing = Array.BinarySearch(data, 6); // 음수 반환
int insertionIndex = ~idxMissing; // 6이 들어갈 삽입 위치

// 리스트에서도 동일한 패턴
var list = new List<int> { 1, 3, 5, 7, 9 };
int li = list.BinarySearch(5); // 2
int liMissing = list.BinarySearch(4); // 음수
int insertPos = ~liMissing;

찾지 못하면 음수(~삽입위치)를 반환합니다. 이 값으로 삽입 위치를 빠르게 얻을 수 있어 이진 탐색 트리나 정렬 유지 컬렉션에 유용합니다.

3. 커스텀 타입과 비교자

커스텀 객체는 IComparer<T> 또는 IComparable<T>를 사용해 정렬/검색 기준을 명확히 해야 합니다.

public record Product(int Id, string Name);

public sealed class ProductIdComparer : IComparer<Product>
{
    public int Compare(Product? x, Product? y)
        => (x?.Id ?? 0).CompareTo(y?.Id ?? 0);
}

var products = new List<Product>
{
    new(2, "Mouse"),
    new(1, "Keyboard"),
    new(4, "Monitor"),
    new(3, "USB Hub")
};

var cmp = new ProductIdComparer();
products.Sort(cmp); // Id 기준으로 정렬

// 검색 키와 동일 기준 사용
int index = products.BinarySearch(new Product(3, string.Empty), cmp);
Product? found = index >= 0 ? products[index] : null;

정렬할 때 사용한 비교자와 BinarySearch에 전달하는 비교자가 반드시 동일해야 합니다. 다를 경우 결과가 보장되지 않습니다.

4. 성능 비교: BinarySearch vs Linear Search

간단한 Stopwatch 기반 비교 예제입니다. 정확한 벤치마크는 BenchmarkDotNet 사용을 권장합니다.

using System;
using System.Diagnostics;
using System.Linq;

static class Program
{
    static void Main()
    {
        const int n = 100_000;     // 데이터 크기
        const int q = 1_000;       // 질의 수
        var rnd = new Random(42);

        // 데이터 생성 및 정렬 (중복 포함 가능)
        int[] arr = Enumerable.Range(0, n).Select(_ => rnd.Next(0, n * 4)).ToArray();
        Array.Sort(arr);

        // 질의 생성 (존재/부재 섞기)
        int[] queries = Enumerable.Range(0, q).Select(_ => rnd.Next(0, n * 4)).ToArray();

        // JIT 워밍업
        _ = Array.BinarySearch(arr, queries[0]);
        _ = LinearSearch(arr, queries[0]);

        // BinarySearch 측정
        var sw = Stopwatch.StartNew();
        long binSum = 0;
        for (int i = 0; i < q; i++)
            binSum += Array.BinarySearch(arr, queries[i]);
        sw.Stop();
        Console.WriteLine($"BinarySearch: {sw.ElapsedMilliseconds} ms, sum={binSum}");

        // LinearSearch 측정
        sw.Restart();
        long linSum = 0;
        for (int i = 0; i < q; i++)
            linSum += LinearSearch(arr, queries[i]);
        sw.Stop();
        Console.WriteLine($"LinearSearch: {sw.ElapsedMilliseconds} ms, sum={linSum}");
    }

    static int LinearSearch(int[] arr, int key)
    {
        for (int i = 0; i < arr.Length; i++)
            if (arr[i] == key) return i;
        return -1;
    }
}

실행 환경에 따라 다르지만, 일반적으로 q가 수백~수천, n이 수만 이상이면 BinarySearch가 선형 검색보다 수배 이상 빠릅니다. 특히 데이터가 클수록 격차가 커집니다.

5. 결과 해석과 실전 팁

- 데이터가 충분히 크고 검색이 빈번하면: 정렬 + BinarySearch가 유리합니다.
- 데이터가 매우 작거나 검색이 드물면: 정렬 비용을 고려해 단순 선형 검색도 충분히 빠를 수 있습니다.
- 삽입/삭제가 잦은 경우: 매번 정렬 비용이 커질 수 있으니, 정렬 유지 구조나 해시(딕셔너리/셋)도 후보입니다.
- 정확한 측정: 릴리즈 빌드, 서버 GC, 다회 반복, BenchmarkDotNet 사용을 권장합니다.

6. 자주 하는 실수와 체크리스트

- 정렬 누락: BinarySearch는 정렬된 컬렉션에서만 올바르게 동작합니다.
- 비교자 불일치: Sort와 BinarySearch에 같은 IComparer<T>를 사용해야 합니다.
- 중복 처리: 중복값이 있을 때 특정 인덱스(첫/마지막)를 원하면 이웃을 확장 스캔하거나 LowerBound/UpperBound 패턴을 구현합니다.
- 음수 결과 처리: ~index로 삽입 위치를 정확히 계산합니다.

7. 요약

BinarySearch는 대규모 데이터에서 빠른 O(log n) 탐색을 제공하며, 올바른 정렬과 비교자 일관성이 핵심입니다. 작은 데이터나 일회성 검색은 선형 검색이 단순하고 충분히 빠를 수 있습니다. 작업 부하와 데이터 특성을 기준으로 정렬 비용, 검색 빈도, 업데이트 빈도를 함께 고려해 선택합니다.