Представьте, что у вас есть действительно длинный список чисел, расположенных в порядке возрастания или убывания, и вы просто ищете одно число из действительно длинного списка. Очевидно, что просмотр длинного списка до тех пор, пока вы не найдете свой номер, будет довольно напряженной задачей, и не только это, но вы, вероятно, потратите много времени, пока занимаетесь этим. Поэтому остается только гадать, есть ли какой-нибудь способ выполнить эту задачу, не теряя так много времени и не торопясь.
Так что же нам делать? Что ж, мы посмотрим на это с точки зрения программиста, напишем простой код, который может выудить искомое число из большого списка, и все готово, не так ли? Не совсем так. В зависимости от того, сколько переменных смешано с этим числом, которое мы ищем, скорость обработки программы будет становиться все медленнее и медленнее.
Вот где проявляется эффективность алгоритма двоичного поиска.
Что такое алгоритм двоичного поиска?
Эта функция позволяет быстрее и проще находить определенное число из большого набора чисел, упорядоченных по порядку. Проще говоря, он ищет иголку в стоге сена.
Эта программа ищет заданное число, располагая их по порядку, разделяя их на две половины и просматривая половину за раз.
Поскольку числа расположены в порядке (либо по возрастанию, либо по убыванию), код принимает длину чисел в списке (количество чисел в обрабатываемой последовательности), начиная с нуля до любого общего количества числа есть, и делит его на два в поисках среднего числа в списке чисел.
Возьмем, к примеру, таблицу выше. Число, которое мы ищем, - двадцать три (23).
Как видно из таблицы, поля пронумерованы от нуля (0) до девяти (9). В полях расположены случайные числа в порядке возрастания.
Затем код находит среднее число в списке чисел. Есть десять (10) квадратов, каждая с числом в них, как показано на рис. 1. Код делит десять (10) на два (2), чтобы найти среднее число, которое в случае рис. 2 равно шестнадцати (16).
Теперь начинается основной поиск. Код берет число, которое мы ищем (назовем его отсутствующим числом (23)), и помещает его рядом со средним числом (16), затем он определяет большее число. В этом случае недостающее число больше среднего числа. Поскольку числа расположены в порядке возрастания, недостающее число будет расположено справа от среднего числа, все, что находится слева от среднего числа, включая среднее число, будет отброшено, потому что недостающее число больше, чем оно есть.
Весь процесс будет повторяться для всех чисел справа от среднего числа (16), включая поиск нового среднего числа.
Процесс повторяется с теми же принципами, пока не будет найден недостающий номер.
Написание кода алгоритма двоичного поиска
Чтобы использовать алгоритм двоичного поиска в Python, нам нужно сначала его определить. Его определение в основном похоже на написание формулы для математической задачи до ее решения, тогда как в этом случае определение важно, потому что до сих пор python не знал формулу для алгоритма двоичного поиска, поэтому мы определяем это в начале под заданным именем (Binary_Search) и дать программе параметры, чтобы знать, какая строка кода должна быть выполнена и когда.
На рис. 4 показаны первые три строки моего кода. Здесь я просто установил параметры, на которых в основном ориентирован алгоритм.
«Число», которое представляет все числа в списке, и «Элемент», представляющее конкретное число, которое мы ищем.
Затем мы хотим определить первое и последнее числа в списке, они представлены как «слева» для первого числа в списке и «справа» для последнего числа в списке. Вторая строка предназначена для кода, чтобы начать отсчет чисел с нуля. Для дальнейшего объяснения предположим, что все числа в списке расположены бок о бок в прямоугольниках, как и на первых трех рисунках, первое поле нумеруется.
Третья строка кода в основном сообщает системе: «После того, как вы подсчитаете общее количество ящиков (чисел), минус один из результата и используйте ответ как число для последнего ящика». Если вам интересно, почему он должен быть минус один, это потому, что первое поле имеет номер «0», и когда программа считает поля, он начинается с «1».
Первые две строки кода на рис. 5 сообщают программе, как найти средний прямоугольник. он берет первое поле с номером '0' и добавляет его к номеру последнего поля, затем он делится на два, результат находится среди ящиков, которые уже пронумерованы от '0' до любого общего количества чисел является.
Строка номер девять (9) - это место, где начинается основной код двоичного поиска. когда программа достигает этой точки, она берет недостающее число и доводит его до среднего числа, если оно меньше среднего числа, программа отбрасывает все, что находится справа от среднего числа, включая среднее число, это потому, что задействованные числа расположены в порядке возрастания.
Если недостающее число больше среднего, программа отбрасывает все, что находится слева от среднего числа, включая среднее число. Если среднее число совпадает со средним числом, значит, недостающее число было обнаружено.
Теперь, работая над собственным проектом, я решил использовать гораздо больший диапазон чисел. Как видно на рис. 6, я использовал диапазон чисел от нуля «0» до ста миллионов «100000000» и настроил программу на поиск числа «5 426 998».
Если вы помните, на рис. 4 я определил двоичный поиск с помощью «числа» и «элемента» в скобках рядом с ним. На рис. 6 я вернул эту строку с «order_list» вместо «number» и «search_item» вместо «item». При запуске кода эти представления заменят представления исходной формулы на рис. 4.
Остальная часть кода сообщает программе, что нужно печатать число, когда оно будет найдено. Если номер не найден, код напечатает «не найден», что означает, что отсутствующий номер не входит в диапазон номеров, которые искала программа.
Алгоритм двоичного поиска в повседневной жизни
Все это время я говорил о том, как двоичный поиск упрощает и ускоряет поиск вещей. Можно было бы задаться вопросом, применяется ли он только к числам, ну, он выходит за рамки простых чисел. Фактически, многие из нас применяют двоичный поиск к тому, что мы делаем каждый день, и мы даже не осознаем этого, я, например, никогда этого не осознавал, пока не подумал об этом.
Самый простой пример двоичного поиска в повседневной жизни - поиск чего-либо в словаре. Предполагая, что вы ищете алфавит 'K', естественно, вы откроете словарь на любой странице в случайном порядке, в зависимости от того, на какой странице алфавита вы случайно открыли, если алфавит стоит после 'K', вы откажетесь алфавит, а также все, что после него, и если оно до 'K', вы отбросите алфавит, а также все, что перед ним. Здесь задействован базовый двоичный поиск.
Дело не только в использовании словарей, когда вы ищете конкретную главу в романе, который читаете, и так далее.
