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

Задавлись ли вы вопросом, в очередной раз используя поиск файлов в ОС, за которой работаете, почему он выполняется так медленно? Нет, даже тааааааак медленно? И если на MacOS этим поиском хотя бы можно пользоваться (но до идеала, само собой, далеко), то на Windows поиск может занимать часы (с настройками по умолчанию). А можно так и не найти ничего, несмотря на то, что запрашиваемый файл существует)). При всем при этом мы сейчас говорим о поиске файлов по имени — простейший поиск. Заикаться по поводу поиска по содержимому, думаем, даже не стоит. Но давайте обратим внимание на поиск в интернете. Любой поисковик позволяет произвести поиск по содержимому всего (доступному для поиска, разумеется) интернета за доли секунды, выдавая триллионы результатов. И при всем при этом на поиск локального файла по имени порой могут уходить минуты, а то и часы. Само собой, существуют сторонние решения, позволяющие многократно ускорить выполнение поиска на локальной машине (как минимум под Windows это точно). С помощью стороннего (к сожалению) софта мы можем находить все (абсолютно все) файлы на компьютере по мере набора поискового запроса, т.е. за те же доли секунды (а то и быстрее), что, конечно, невероятно приятно и удобно. Вот бы весь интерфейс ОС был настолько отзывчивым (но это скорее всего из области фантастики…). После непродолжительного использования такого софта смысла во встроенном в ОС поиске становится все меньше). Но мы сегодня здесь собрались не для того, чтобы обсуждать проблемы и изъяны современных ОС, а для того, чтобы обсудить один алгоритм, благодаря которому настолько быстрый поиск в интернете (и как мы уже выяснили, не только в интернете) вообще возможен.

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

Как вы уже знаете из заглавия статьи, речь сегодня пойдет об алгоритме двоичного или бинарного поиска. Двоичный поиск — это классический алгоритм, позволяющий найти (и, как позже мы выясним, очень быстро найти) элемент в отсортированном массиве. Не побоимся этого слова — фундаментальный алгоритм. Двоичный поиск — своего рода естественный алгоритм, т.к. люди могут им пользоваться, даже не осознавая этого. Самый простейший пример двоичного поиска в жизни — это то, как мы обычно находим необходимое слово в словаре. Мы открываем словарь примерно на середине (или ближе к началу/концу, в зависимости от положения первой буквы слова в алфавите), далее мы повторяем операцию для следующей буквы искомого слова (само собой, люди делают это не идеально), до тех пор пока искомое слово не будет найдено.

Чуть более формально алгоритм задается следующим образом:

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

Пример:

Дан массив:

var numbers = new[] {1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71};

1	var numbers = new[] {1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71};

в котором нужно найти индекс числа 7 . На первом шаге выбираем центральный элемент массива. Т.к. массив состоит из 17 элементов, то центральным элементом будет число под индексом 8, а именно 14:

{1, 3, 4, 6, 7, 8, 10, 13, |14|, 18, 19, 21, 24, 37, 40, 45, 71}

1	{1, 3, 4, 6, 7, 8, 10, 13, \|14\|, 18, 19, 21, 24, 37, 40, 45, 71}

Далее мы сравниваем 14 с искомым числом и, т.к. 14 — это не искомое число, и 14 больше, чем искомое число, то продолжаем поиск в меньшей части массива, а именно [0..7] . Следующим элементом для сравнения будет число 6 под индексом 3:

{1, 3, 4, ||6||, 7, 8, 10, 13, |14|, 18, 19, 21, 24, 37, 40, 45, 71}

1	{1, 3, 4, \|\|6\|\|, 7, 8, 10, 13, \|14\|, 18, 19, 21, 24, 37, 40, 45, 71}

Так как число 6 не равно искомому числу и оно меньше искомого, то поиск продолжаем в большей части массива, а именно [4..7] . Следующим элементом для сравнения будет число 8, под индексом 5.

{1, 3, 4, ||6||, 7, |||8|||, 10, 13, |14|, 18, 19, 21, 24, 37, 40, 45, 71}

1	{1, 3, 4, \|\|6\|\|, 7, \|\|\|8\|\|\|, 10, 13, \|14\|, 18, 19, 21, 24, 37, 40, 45, 71}

Поступаем аналогичным образом: 8 не равно 7 и больше 7; следовательно, продолжаем поиск в меньшей части оставшегося массива, а именно [4..4] . Следующим и последним числом в нашем поиске будет число 7 — искомое число, которое находится под индексом 4 в нашем списке:

{1, 3, 4, ||6||, ||||7||||, |||8|||, 10, 13, |14|, 18, 19, 21, 24, 37, 40, 45, 71}

1	{1, 3, 4, \|\|6\|\|, \|\|\|\|7\|\|\|\|, \|\|\|8\|\|\|, 10, 13, \|14\|, 18, 19, 21, 24, 37, 40, 45, 71}

Сложности в реализации

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

Двоичный поиск — это очень простой (по сравнению с большинством других алгоритмов) алгоритм, который на самом деле не так-то просто реализовать корректно на практике. Давайте процитируем слова Иона Бентли (Jon Bentley), американского ученого в области компьютерных наук, своим студентам:

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

Насколько алгоритм двоичного поиска прост с первого взгляда, примерно настолько же легко реализовать его неправильно. Согласно Дональду Кнуту (из книги «Sorting and Searching»), впервые идея двоичного поиска была опубликована в 1946 году. Но потребовалось, ни много, ни мало, а целых 12 лет для того, чтобы был опубликован первый безошибочный вариант кода двоичного поиска. Ион Бентли утверждает, что он давал это задание как своим студентам, так и профессиональным программистам, и по статистике только ~10% программистов могут написать этот алгоритм с первого раза без ошибок. А самое смешное (смех сквозь слезы?) — это то, что официальный алгоритм Ион Бентли (который многократно публиковался, и неизвестно, сколько раз был использован в продакшене), также оказался не без греха. Но найти подобную ошибку, скажем так, не просто. Возможно, этот рассказ вам кажется какой-то древней историей (или даже сказкой, которой любят пугать…), и уж сейчас-то явно такого быть не может… Но на момент 2006 года — почти все реализации JDK содержали подобную ошибку в алгоритмах двоичного поиска и сортировки слиянием. Глупо надеяться, что через 14 лет нет шанса нарваться на подобную ошибку на проде. Последствия этого, само собой, печальные. И это — еще один урок, яркими красками описывающий, почему слепое (бездумное) копирование кода (неважно, копируете вы со stackoverflow.com или из книги по алгоритмам) опасно. Ошибки нас поджидают за углом даже в самых простых алгоритмах и в самом маленьком по объему коде.

Глобально ошибки в реализации двоичного кода можно разделить на следующие группы:

алгоритм не работает с массивами из 0/1/2 элементов;
алгоритм не находит первый или последний элемент;
алгоритм некорректен, если элемента нет в массиве;
алгоритм некорректен, если массив содержит повторяющиеся элементы;
обращение к элементам за пределами массива;
баг из JDK (о котором чуть позже).

Давайте кратко рассмотрим несколько реальных реализаций, которые содержат одну (а. возможно, и больше) ошибок из списка выше. Пример на C#:

public static int BinarySearch(int[] data, int asked)
{
    var index = 0;
    var work = true;
    var leftEdge = 0;
    var rightEdge = data.Length - 1;

    do
    {
        index = rightEdge - leftEdge;
        if (index / 2 > 0)
        {
            if (data[index] > asked)
            {
                rightEdge = index;
            }
            else if (data[index] < asked)
            {
                leftEdge = index;
            }
            else if (data[index] == asked)
            {
                return index;
            }
        }
        else
        {
            return -1;
        }
    } while (work);

    return -1;
}

public static int BinarySearch(int[] data, int asked)

{

var index = 0;

var work = true;

var leftEdge = 0;

var rightEdge = data.Length - 1;

{

index = rightEdge - leftEdge;

if (index / 2 > 0)

{

if (data[index] > asked)

{

rightEdge = index;

}

else if (data[index] < asked)

{

leftEdge = index;

}

else if (data[index] == asked)

{

return index;

}

else

{

return -1;

}

} while (work);

return -1;

}

Вышеприведенный код зависает, например, при следующих входных данных: var numbers = new[] {2, 4, 6, 8, 10}; и var value = 2; .

Пример на Java:

static int binsearch(int[] a, int key)
{
    int n = a.length;
    int lo = 0;
    int hi = n - 1;

    while (lo < hi)
    {
        int mid = (lo + hi) / 2;
        if (key > a[mid])
            lo = mid + 1;
        else
            hi = mid;
    }

    return a[hi] == key ? hi : -1;
}

static int binsearch(int[] a, int key)

{

int n = a.length;

int lo = 0;

int hi = n - 1;

while (lo < hi)

{

int mid = (lo + hi) / 2;

if (key > a[mid])

lo = mid + 1;

else

hi = mid;

}

return a[hi] == key ? hi : -1;

}

Этот код, как минимум, не учитывает, что массив может быть пустым.

Еще один пример на C#:

static int? getIndexOf(int[] A, int val)
{
    var first = 0;
    var count = A.Length;

    while (count > 1)
    {
        count = count / 2;
        var i = first + count - 1;
        if (A[i] == val) return i;
        if (A[i] < val) first += count;
    }

    if (count == 1)
        return A[first] == val ? (int?) first : null;

    return null;
}

static int? getIndexOf(int[] A, int val)

{

var first = 0;

var count = A.Length;

while (count > 1)

{

count = count / 2;

var i = first + count - 1;

if (A[i] == val) return i;

if (A[i] < val) first += count;

}

if (count == 1)

return A[first] == val ? (int?) first : null;

return null;

}

Этот код не может найти последний элемент в массиве.

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

public static int buggyBinarySearch(int[] a, int target) {
    int low = 0;
    int high = a.length - 1;
    
    while (low <= high) {
        int mid = (low + high) / 2;
        int midVal = a[mid];
        
        if (midVal < target)
            low = mid + 1;
        else if (midVal > target)
            high = mid - 1;
        else
            return mid;
    }
    return -1;
}

public static int buggyBinarySearch(int[] a, int target) {

int low = 0;

int high = a.length - 1;

while (low <= high) {

int mid = (low + high) / 2;

int midVal = a[mid];

if (midVal < target)

low = mid + 1;

else if (midVal > target)

high = mid - 1;

else

return mid;

}

return -1;

}

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

int mid = (low + high) / 2;

1	int mid = (low + high) / 2;

Попробуйте догадаться, что в ней может быть не так. Так как мы достаточно сильно сузили проблемный участок, сделать это, должно быть, легче, чем на предыдущем шаге. Догадались? Поздравляю! А если нет, то не беда, ответ под спойлером:

Ответ

Проблема в том, что сумма low и high может быть больше Integer.MAX_VALUE, из-за чего произойдет переполнение, и, как следствие, мы получим отрицательное число.

[свернуть]

Как же это можно исправить? Самый простой вариант:

int mid = low + ((high - low) / 2);

1	int mid = low + ((high - low) / 2);

Или, если хочется чего-то более неординарного, то можно так:

int mid = (low + high) >>> 1;

1	int mid = (low + high) >>> 1;

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

Сложность алгоритма

Выше мы уже вскользь упоминали, что двоичный поиск работает очень быстро. Но очень быстро — это как? Асимптотическая сложность двоичного поиска O(log2N) . Возможно, яснее не стало? Предположим, у нас есть массив из 100 000 000 элементов. Двоичный поиск на таком массиве завершится не позднее 28 шагов. Т.е. чтобы определить, содержит ли наш массив искомое число, потребуется не более 28 сравнений. И это невероятно быстро. Цена этому, конечно, память. Но память нынче практически ничего не стоит (если это, конечно, не память для мака). Можно задуматься, что, возможно, выгоднее в подобных сценариях использовать хэштаблицы. Т.к. в таком случае время поиска составит O(1) . Да, возможно, оно так и есть, а, возможно, и нет. Все зависит от входных данных. В среднем хэштбалицы будут использовать больше памяти, и заполнение таблицы будет занимать больше времени, а вот поиск, скорее всего, будет несколько быстрее. Опять-таки, все очень сильно зависит от используемых алгоритмов в реализации хештаблиц и используемых данных/алгоритма хэширования, т.к. легко получить ситуацию (из-за коллизий), что время поиска упадет до невероятных (по сравнению с двоичным поиском) O(n) . Про это также не стоит забывать. Само собой, нельзя не упомянуть сложность алгоритмов, реализующих работу хэштаблиц, и, как мы теперь знаем, с большой долей вероятности, в них тоже есть еще не найденные проблемы, которые легко могут привести, как минимум, к замедлению работы хэштаблиц.

Ну, а на сегодня — все, увидимся в следующей статье. Ах, да, чуть не забыли, а какой алгоритм/структуру данных разобрать в следующей статье? Пишите свой вариант в комментариях под этим постом. До скорых встреч, и беспроблемных вам алгоритмов!

Добавить комментарий Отменить ответ

Для отправки комментария вам необходимо авторизоваться.

1 комментарий

Sergius:

02.01.2021 в 12:48

Отличная статья!
В конце статьи автор предложил альтернативу такому поиску — хештаблицы. Хотелось бы подробнее узнать про них и, в особенности, про неправильное использование этой структуры данных.

Войдите, чтобы ответить