Алгоритмы и структуры данныхДвоичный поиск

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

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

Идея бинарного поиска заключается в «разделяй и властвуй», непрерывно деля количество элементов-кандидатов пополам на каждой итерации. Это свойство позволяет алгоритму иметь временную сложность O(log n).

Плюсы

• O(log n) временная сложность. Это один из самых быстрых алгоритмов поиска;
• Это просто реализовать;
• Это легко понять;

Минусы

• Он работает только с отсортированными массивами;
• Временная сложность вставки составляет O(log n). Я отношу это к минусам, потому что существуют алгоритмы с O(1) временной сложностью для вставки, но во многих случаях это не имеет большого значения, потому что O(log n) по-прежнему очень хорошая производительность;

Требования

• Массив должен быть отсортирован;
• Для использования алгоритма бинарного поиска массив должен иметь произвольный доступ, что означает, что доступ к элементам возможен с использованием их индекса;
• Данные, хранящиеся в массиве, должны иметь тип, поддерживающий сравнение. Например, a ‹ b, a › b, a == b;
• Сравнение, используемое для поиска значения в массиве, должно быть таким же, которое используется для сортировки или вставки значений в массив;

Временная сложность (бинарный поиск против линейного поиска)

Демонстрационная анимация

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

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

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

    while (left <= right)
    {
        var middle = left + ((right - left) / 2);
        if (array[middle] == search)
        {
            return middle;
        }

        if (array[middle] < search)
        {
            left = middle + 1;
        }
        else
        {
            right = middle - 1;
        }
    }

    return -1;
}

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

static int BinarySearch(int[] array, int search, int left, int right)
{
    while(left <= right)
    {
        var middle = left + ((right - left) / 2);

        if(search == array[middle])
        {
            return middle;
        }

        if(search > array[middle])
        {
            return BinarySearch(array, search, middle + 1, right);
        }

        return BinarySearch(array, search, left, middle - 1);
    }

    return -1;
}

Несколько советов по реализации бинарного поиска

Нашел средний индекс

Очень часто средний индекс вычисляется как (left + right) / 2, но это не лучший способ сделать это. Если массив очень большой, сумма left и right может превысить максимальное значение целочисленного типа. Чтобы избежать этой проблемы, мы можем использовать следующую формулу: слева + ((справа — слева) / 2).

Давайте разберем эту формулу по частям, чтобы понять проблему.

Console.WriteLine($"MaxInt: {int.MaxValue:n0}"); // MaxInt: 2 147 483 647

var left = int.MaxValue - 1_000;
var right = int.MaxValue - 300;

Console.WriteLine($"left: {left:n0}"); // left: 2 147 482 647
Console.WriteLine($"right: {right:n0}"); // right: 2 147 483 347

// Bad why
var badWhyStep1 = left + right;
Console.WriteLine($"Bad why -> left + right: {badWhyStep1:n0}"); // Bad why -> left + right: -1 302
var badWhyStep2 = badWhyStep1 / 2;
Console.WriteLine($"Bad why -> (left + right) / 2: {badWhyStep2:n0}"); // Bad why -> (left + right) / 2: -651

// Good why
var goodWhyStep1 = right - left;
Console.WriteLine($"Good why -> right - left: {goodWhyStep1:n0}"); // Good why -> right - left: 700
var goodWhyStep2 = goodWhyStep1 / 2;
Console.WriteLine($"Good why -> (right - left) / 2: {goodWhyStep2:n0}"); // Good why -> (right - left) / 2: 350
var goodWhyStep3 = left + goodWhyStep2;
Console.WriteLine($"Good why -> left + ((right - left) / 2): {goodWhyStep3:n0}"); // Good why -> left + ((right - left)) / 2: 2 147 482 997 // right: 2 147 483 147

Как видите, для большого массива операция left + right может переполнить максимальное значение целочисленного типа и вернуть значение Wearg.

Использовать оператор сдвига

Во встроенной реализации бинарного поиска некоторых языков можно увидеть использование оператора сдвига ›› 1 для деления значения на 2.
Во-первых, мы можем сделать это, потому что сдвиг операция ››1 эквивалентна делению на 2. Во-вторых, потому что побитовые операции более близки к машинному коду и могут быть быстрее операции деления.

До

var middle = left + ((right - left) / 2);

После

var middle = left + ((right - left) >> 1);

Возвращает дополнение индекса, если значение не найдено

В предыдущих примерах я возвращал -1, когда значение не было найдено. Использование условия index ‹ 0 служит индикатором того, что значение не было найдено. Однако предположим, что мы также хотим использовать ту же реализацию для определения следующего подходящего индекса для вставки значения. В этом сценарии индекс -1 не особенно полезен.

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

Имея это в виду, если значение не найдено, мы можем просто использовать оператор ~. Этот оператор инвертирует все биты, включая бит знака, в результате чего получается отрицательное значение. Мы можем использовать это отрицательное значение, чтобы показать, что значение не найдено. Однако, если мы применим операцию дополнения еще раз, мы получим позицию, в которую нужно вставить значение. Этот подход позволяет нам использовать одну и ту же реализацию как для поиска значения, так и для определения следующей возможной точки вставки.

public void Add(int item)
{
    var position = Search(item);
    if(position < 0)
    {
        position = ~position;
    }
    items.Insert(position, item);
}

public int Search(int item)
{
    // ...
    // When the value is not found
    return ~left;
}

Двоичный поиск не только для чисел

Алгоритм бинарного поиска работает не только с числами. Его можно использовать с любым типом данных, который поддерживает сравнение. Например, в C# вы можете создать класс и реализовать интерфейс IComparable для определения логики сравнения.

public int BinarySearch(T item)
{
    var left = 0;
    var right = _items.Count - 1;

    while(left <= right)
    {
        var middle = left + ((right - left) >> 1);

        if(_items[middle].CompareTo(item) == 0)
        {
            return middle;
        }

        if(_items[middle].CompareTo(item) < 0)
        {
            left = middle + 1;
        }
        else
        {
            right = middle - 1;
        }
    }

    return ~left;
}

public class Person : IComparable<Person>
{
    public string? FirstName { get; set; }
    public string? LastName { get; set; }
    public int Age { get; set; }

    public int CompareTo(Person? other)
    {
        if(other is null)
        {
            return -1;
        }

        var result = Age.CompareTo(other.Age);
        if(result != 0)
        {
            return result;
        }

        result = compareTo(FirstName, other?.FirstName);
        if(result != 0)
        {
            return result;
        }

        return compareTo(LastName, other?.LastName);


        static int compareTo(string? left, string? right)
        {
            if(left is null && right is null)
            {
                return 0;
            }

            if(left is null)
            {
                return -1;
            }

            if(right is null)
            {
                return 1;
            }

            return left.CompareTo(right);
        }
    }
}

Полный пример доступен на мой GitHub