Алгоритм двоичного поиска

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

Двоичный поиск



Когда вам нужно найти позицию элемента в сортируемой коллекции, алгоритм двоичного поиска обеспечивает подходящий и быстрый подход. Этот алгоритм включен в общий класс List , который был внедрен в .NET framework версии 2.0. Хотя это означает, что вам обычно не требуется воссоздать его, интересно понять, как работает этот алгоритм.

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

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

В действительности, обычно неэффективно фактически удалять элементы из массива или коллекции. Гораздо более вероятно, что вы будете использовать указатели для определения первого и последнего индекса поиска. Они инициализируются, чтобы указывать на первый и последний элементы в последовательности, и один из указателей перемещается во время каждой итерации, чтобы уменьшить вдвое эффективную длину коллекции.

Давайте рассмотрим пример, используя приведенные ниже значения, ищем номер тридцать шесть.

10, 15, 18, 25, 29, 31, 36, 41, 44, 48, 49, 50, 52, 54, 58, 61, 65, 70, 95, 99

На первой итерации мы начнем с определения середины. Поскольку в коллекции есть четное количество элементов, мы можем выбрать либо десятый, либо одиннадцатый элемент. Решение произвольное, поэтому давайте использовать самые левые из средних значений, что составляет сорок восемь.

10, 15, 18, 25, 29, 31, 36, 41, 44, [48], 49, 50, 52, 54, 58, 61, 65, 70, 95, 99

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

10, 15, 18, 25, [29], 31, 36, 41, 44

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

31, [36], 41, 44 

Реализация

Давайте реализуем алгоритм бинарного поиска с использованием C# . Мы создадим метод для выполнения двоичного поиска по отсортированному массиву целых чисел. Будем считать, что массив отсортирован в порядке возрастания. Возвращаемое значение для метода будет индексом элемента поиска или -1, если элемент не найден.

Для начала добавьте следующую сигнатуру метода в класс, который был автоматически сгенерирован при создании проекта. Метод имеет два параметра. Первый получает массив для поиска, а второй - номер.

public static int SearchBinary(int[] items, int find)
{
}

Вместо того, чтобы пытаться уменьшить размер массива во время каждой итерации, мы будем использовать указатели для начала и конца «куска» массива, в котором находится ищущийся элемент. В начале процесса это весь массив. Поэтому указатель начала будет указывать на нулевой индекс, а конечный указатель будет меньше длины массива.

Чтобы настроить указатели и вызвать итеративную часть алгоритма, добавьте следующий код в метод SearchBinary:

int numStart = 0;
int numEnd = items.Length - 1;
return Find(items, find, numStart, numEnd);

Рекурсивный метод поиска

Рекурсивная часть алгоритма имеет четыре части:

1. Убедитесь, что начальные и конечные указатели все еще действительны, указав длину массива, которая больше нуля. Если элемент, который мы ищем, не существует в массиве, после последней итерации начальные и конечные указатели будут перекрываться, давая кусок массива без элементов. Если это произойдет, мы вернем -1, чтобы указать, что элемент отсутствует.
2. Найдите индекс средней точки остальных предметов. Это легко вычисляется с использованием указателя начала и длины оставшегося элемента.
3. Проверьте, является ли элемент в средней точке значением, которое мы хотим найти. Если это так, мы вернем индекс средней точки, и алгоритм закончится.
4. Убедитесь, что элемент в средней точке больше, чем поисковый запрос. Если это так, мы переместим конечный указатель на один элемент до середины и начнем следующую итерацию с шага 2 выше. Если нет, среднее значение должно быть меньше, чем элемент поиска, поэтому мы переместим указатель начала на элемент сразу после середины и вернемся к шагу 2.

Вы можете увидеть эти шаги в коде метода ниже:

	private static int Find(int[] items, int find, int start, int end)
{
    int chunkSize = 1 + (end - start);
 
    if (chunkSize == 0)
        return -1;
 
    int midpoint = start + (chunkSize / 2);
 
    if (items[midpoint] == find)
        return midpoint;
    else if (items[midpoint] > find)
        return Find(items, find, start, midpoint - 1);
    else
        return Find(items, find, midpoint + 1, end);
}

Чтобы опробовать алгоритм поиска, добавьте следующий код в метод main и пошаговое выполнение кода в отладчике, чтобы увидеть результаты, либо добавьте в конце Console.WriteLine(index);.

int[] items = new int[]
    { 10, 15, 18, 25, 29, 31, 36, 41, 44, 48, 49, 50, 52, 54, 58, 61, 65, 70, 95, 99 };
int index;
index = SearchBinary(items, 36);