Алгоритм двоичного поиска с ПРИМЕРОМ

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

Что такое поиск?

Поиск — это утилита, которая позволяет пользователю находить документы, файлы, мультимедиа или любые другие типы данных, хранящиеся в базе данных. Поиск работает по простому принципу сопоставления критериев с записями и отображения их пользователю. Таким образом работает самая основная функция поиска.

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

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

Как работает двоичный поиск?

Бинарный поиск работает следующим образом:

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

Алгоритм бинарного поиска (псевдокод)

Бинарный поиск можно представить в виде короткой итеративной процедуры. Она хранит два указателя, нижний и верхний, и сужает диапазон до тех пор, пока не будет найдена цель или диапазон не станет пустым.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

В случае успеха подпрограмма возвращает индекс целевого значения, а в случае отсутствия значения — -1. Поскольку диапазон уменьшается вдвое при каждом проходе, цикл выполняется не более log₂(n) раз.

Пример двоичного поиска

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

На изображении выше показано следующее:

1. У вас есть массив из 10 цифр, и нужно найти элемент 59.
2. Все элементы помечены индексами от 0 до 9. Теперь вычисляем середину массива. Для этого берем левое и правое значения индекса и делим их на 2. Результат равен 4.5, но мы берем целую часть. Следовательно, середина — это 4.
3. Алгоритм удаляет все элементы от середины (4) до нижней границы, потому что 59 больше 24, и теперь в массиве остается только 5 элементов.
4. Теперь 59 больше 45 и меньше 63. Середина равна 7. Следовательно, значение правого индекса становится средним − 1, что равно 6, а значение левого индекса остается таким же, как и раньше, то есть равным 5.
5. На данный момент вы знаете, что 59 идет после 45. Следовательно, левый индекс, равный 5, также становится средним.
6. Эти итерации продолжаются до тех пор, пока массив не сократится до одного элемента или пока искомый элемент не станет серединой массива.

Пример 2

Рассмотрим следующий пример, чтобы понять, как работает бинарный поиск.

1. У вас есть массив отсортированных значений от 2 до 20, и вам нужно найти 18.
2. Среднее арифметическое нижнего и верхнего пределов равно (l + r) / 2 = 4. Искомое значение больше среднего, которое равно 4.
3. Значения массива меньше среднего значения отбрасываются из поиска, а значения больше среднего значения (4) продолжают поиск.
4. Это повторяющийся процесс деления до тех пор, пока не будет найден фактический элемент, который нужно найти.

Зачем нам нужен двоичный поиск?

Следующие причины делают бинарный поиск лучшим выбором в качестве алгоритма поиска:

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

Узнайте о нашем следующем уроке по теме Линейный поиск: Python, C++ Пример.

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

Бинарный и линейный поиск — два наиболее распространенных способа поиска значения в коллекции. В таблице ниже показано, чем они отличаются:

Вкратце, бинарный поиск намного быстрее при работе с большими отсортированными данными, в то время как линейный поиск проще и является единственным вариантом, когда данные не отсортированы.

Часто задаваемые вопросы (FAQ)