Прежде чем изучать двоичный поиск, давайте узнаем:
Что такое поиск?
Поиск - это служебная программа, которая позволяет пользователю находить документы, файлы, мультимедиа или любые другие типы данных, хранящиеся в базе данных. Поиск работает по простому принципу сопоставления критериев с записями и отображения их пользователю. Таким образом работает самая основная функция поиска.
Что такое двоичный поиск?
Бинарный поиск - это расширенный тип алгоритма поиска, который находит и извлекает данные из отсортированного списка элементов. Его основной принцип работы заключается в разделении данных в списке пополам до тех пор, пока требуемое значение не будет найдено и отображено пользователю в результатах поиска. Двоичный поиск обычно известен как полуинтервальный поиск или логарифмический поиск .
В этом руководстве по алгоритму вы узнаете:
- Что такое поиск?
- Что такое двоичный поиск?
- Как работает двоичный поиск?
- Пример двоичного поиска
- Зачем нужен двоичный поиск?
Как работает двоичный поиск?
Бинарный поиск работает следующим образом:
- Процесс поиска начинается с поиска среднего элемента отсортированного массива данных.
- После этого значение ключа сравнивается с элементом
- Если значение ключа меньше среднего элемента, поиск анализирует верхние значения до среднего элемента для сравнения и сопоставления.
- В случае, если значение ключа больше среднего элемента, поиск анализирует более низкие значения до среднего элемента для сравнения и сопоставления.
Пример двоичного поиска
Давайте посмотрим на пример словаря. Если вам нужно найти определенное слово, никто не просматривает каждое слово последовательно, а случайным образом находит ближайшие слова для поиска нужного слова.
На изображении выше показано следующее:
- У вас есть массив из 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.
- Это повторяющийся процесс деления до тех пор, пока не будет найден фактический элемент для поиска.
Зачем нужен двоичный поиск?
Следующие причины делают бинарный поиск лучшим выбором для использования в качестве алгоритма поиска:
- Двоичный поиск эффективно работает с отсортированными данными независимо от их размера.
- Вместо того, чтобы выполнять поиск, просматривая данные в последовательности, двоичный алгоритм случайным образом обращается к данным, чтобы найти требуемый элемент. Это делает циклы поиска короче и точнее.
- Двоичный поиск выполняет сравнения отсортированных данных на основе принципа упорядочения, а не сравнения на равенство, которые медленнее и в большинстве случаев неточны.
- После каждого цикла поиска алгоритм делит размер массива пополам, поэтому на следующей итерации он будет работать только в оставшейся половине массива.
Резюме
- Поиск - это служебная программа, которая позволяет пользователю искать документы, файлы и другие типы данных. Бинарный поиск - это расширенный тип алгоритма поиска, который находит и извлекает данные из отсортированного списка элементов.
- Двоичный поиск обычно известен как поиск с половинным интервалом или логарифмический поиск.
- Он работает, разделяя массив пополам на каждой итерации, на которой найден требуемый элемент.
- Бинарный алгоритм берет середину массива путем деления суммы значений левого и крайнего правого индекса на 2. Теперь алгоритм отбрасывает нижнюю или верхнюю границу элементов из середины массива, в зависимости от элемента, который нужно найти. .
- Алгоритм случайным образом обращается к данным, чтобы найти требуемый элемент. Это делает циклы поиска короче и точнее.
- Двоичный поиск выполняет сравнения отсортированных данных на основе принципа упорядочения, а не с использованием сравнений на равенство, которые являются медленными и неточными.
- Бинарный поиск не подходит для несортированных данных.