Бинарный поиск на C# с примерами

Обновлено: 31.10.2026 · 6 мин чтения

Как работает бинарный поиск

Алгоритм требует, чтобы данные были отсортированы. Он сравнивает искомое значение со средним элементом. Если значения совпали, поиск окончен. Если искомое меньше, продолжаем в левой половине, если больше - в правой. Так диапазон сжимается вдвое на каждом шаге, и для миллиона элементов хватает около двадцати сравнений вместо миллиона при последовательном переборе.

Представьте поиск слова в бумажном словаре: вы не листаете страницы подряд, а открываете книгу примерно посередине и решаете, в какую сторону идти. Бинарный поиск делает то же самое, только строго пополам. Если же данные не отсортированы, придётся либо сначала отсортировать их, например через быструю сортировку, либо искать последовательным поиском.

Итеративная реализация

Самый частый вариант - цикл с двумя границами. Левая граница left и правая right задают текущий отрезок, на каждой итерации проверяется его середина.

public static int BinarySearch(int[] array, int target)
{
    int left = 0;
    int right = array.Length - 1;

    while (left <= right)
    {
        int mid = left + (right - left) / 2;

        if (array[mid] == target)
            return mid;

        if (array[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;   // элемент не найден
}

Метод возвращает индекс найденного элемента или -1. Условие left <= right важно: если заменить его на строгое неравенство, алгоритм пропустит случай, когда в отрезке остался один элемент.

Почему середина считается именно так

Формула (left + right) / 2 выглядит проще, но при больших индексах сумма может выйти за пределы int и дать отрицательное число. Эта ошибка много лет жила в стандартных библиотеках разных языков. Запись left + (right - left) / 2 безопасна, поскольку разность всегда помещается в диапазон. Для современных массивов .NET длиной до двух миллиардов элементов проблема вполне реальна.

Рекурсивная реализация

Рекурсия лучше передаёт идею "решаем ту же задачу для половины данных", но тратит память на стек вызовов. Глубина здесь логарифмическая, поэтому переполнения стека можно не бояться.

public static int BinarySearchRecursive(int[] array, int target, int left, int right)
{
    if (left > right)
        return -1;

    int mid = left + (right - left) / 2;

    if (array[mid] == target)
        return mid;

    return array[mid] < target
        ? BinarySearchRecursive(array, target, mid + 1, right)
        : BinarySearchRecursive(array, target, left, mid - 1);
}

// вызов
int index = BinarySearchRecursive(data, 42, 0, data.Length - 1);

В production-коде чаще выбирают цикл: он быстрее и не создаёт лишних кадров стека. Рекурсивный вариант удобен для объяснения алгоритма и на собеседованиях.

Обобщённая версия для любых типов

Алгоритм работает не только с числами, но и со строками, датами и своими классами, если у типа есть порядок сравнения. Для этого достаточно ограничить параметр типа интерфейсом IComparable<T>.

public static int BinarySearch<T>(IReadOnlyList<T> list, T target) where T : IComparable<T>
{
    int left = 0, right = list.Count - 1;

    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        int cmp = list[mid].CompareTo(target);

        if (cmp == 0) return mid;
        if (cmp < 0) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

string[] names = { "Анна", "Борис", "Виктор", "Галина", "Дмитрий" };
Console.WriteLine(BinarySearch(names, "Виктор"));   // 2

Строки сравниваются по правилам текущей культуры, поэтому массив должен быть отсортирован тем же способом. Если сортировали через StringComparer.Ordinal, а искать будете с другим сравнением, результат окажется неверным.

Готовые методы .NET

Писать алгоритм вручную нужно редко. В стандартной библиотеке есть несколько вариантов, которые уже протестированы и оптимизированы.

Как и в ручной версии, все эти методы предполагают отсортированные данные. Результат стандартных методов устроен особым образом, об этом ниже.

int[] numbers = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };

int found = Array.BinarySearch(numbers, 23);     // 5
int missing = Array.BinarySearch(numbers, 10);   // отрицательное число

if (missing < 0)
{
    int insertAt = ~missing;                     // позиция вставки: 3
    Console.WriteLine($"Не найден, вставить на позицию {insertAt}");
}

var list = new List<int>(numbers);
Console.WriteLine(list.BinarySearch(56));         // 7

Что возвращает Array.BinarySearch

Если элемент найден, вы получаете его индекс. Если нет, результат отрицательный и равен побитовому отрицанию индекса, куда элемент нужно вставить, чтобы сохранить порядок. Чтобы получить позицию, применяют оператор ~. Это удобно: тот же вызов одновременно отвечает и на вопрос "есть ли элемент", и на вопрос "куда его вставить". Сравнивать результат с -1 нельзя, проверяйте именно < 0.

Поиск границ: первое и последнее вхождение

Если в массиве есть повторы, обычный бинарный поиск вернёт любое из совпадений. Часто нужна левая граница (первое вхождение) или правая (последнее). Такие варианты называют lower bound и upper bound, их используют для подсчёта количества одинаковых значений и для поиска в диапазоне.

// индекс первого элемента, который >= target (или array.Length, если такого нет)
public static int LowerBound(int[] array, int target)
{
    int left = 0, right = array.Length;
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        if (array[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

// индекс первого элемента, который > target
public static int UpperBound(int[] array, int target)
{
    int left = 0, right = array.Length;
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        if (array[mid] <= target) left = mid + 1;
        else right = mid;
    }
    return left;
}

int[] data = { 1, 2, 2, 2, 3, 5, 5, 8 };
int count = UpperBound(data, 2) - LowerBound(data, 2);   // 3 двойки

Здесь правая граница полуоткрытая: right указывает за последний элемент. Такая запись избавляет от лишних поправок на единицу и считается самой устойчивой к ошибкам.

Бинарный поиск по ответу

Идея деления пополам применима не только к массивам. Если есть монотонное условие "для значения x задача выполнима, а для x + 1 тоже", то минимальное подходящее x ищут бинарным поиском прямо по диапазону значений. Так решают задачи про минимальную скорость, максимальную длину отрезка и подбор параметра.

// наименьшее целое x, для которого x * x >= n
public static long CeilSqrt(long n)
{
    long lo = 0, hi = Math.Min(n, 3_037_000_499L);
    while (lo < hi)
    {
        long mid = lo + (hi - lo) / 2;
        if (mid * mid >= n) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Верхняя граница ограничена значением около трёх миллиардов, чтобы квадрат середины не вышел за пределы long. Такие мелочи и составляют основную сложность бинарного поиска на практике.

Типичные ошибки

• Поиск по неотсортированному массиву: алгоритм вернёт неверный результат без исключения.
• Отсортировали по одному правилу, а ищете с другим компаратором, особенно со строками и регистром.
• Зациклились из-за неверного обновления границ: left = mid вместо left = mid + 1 при закрытом отрезке.
• Сравнивают результат Array.BinarySearch с -1 вместо проверки на отрицательное значение.
• Применяют бинарный поиск к LinkedList: доступ по индексу там O(n), и выигрыша нет.
• Забывают про дубликаты и ожидают первое вхождение, хотя метод возвращает любое.

Когда бинарный поиск не лучший выбор

Если поиск выполняется часто, а данные постоянно меняются, поддерживать сортировку дороже, чем искать. Тогда удобнее Dictionary или HashSet с поиском за O(1) в среднем. Если нужен упорядоченный набор с быстрой вставкой, берут SortedSet или дерево, например бинарное дерево поиска. На маленьких массивах до нескольких десятков элементов простой цикл часто не уступает, потому что работает без ветвлений и хорошо ложится в кэш процессора.

Частые вопросы