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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 2

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

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

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

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

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

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

Резюме

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