Двоично търсене в Python: Визуално въведение

Добре дошли

В тази статия ще научите как алгоритъмът за двоично търсене работи зад кулисите и как можете да го внедрите в Python.

По-конкретно ще научите:

• Как алгоритъмът работи зад кулисите, за да намери целеви елемент.
• Как работи неговото изпълнение на Python ред по ред.
• Защо това е много ефективен алгоритъм в сравнение с Линейно търсене.
• Неговите предимства и изисквания.

Нека да започнем! ✨

Въведение в двоично търсене

Този алгоритъм се използва за намиране на елемент в подредена последователност (например: списък, кортеж или низ).

Изисквания

За да приложите алгоритъма за двоично търсене към последователност, последователността вече трябва да бъде сортирана във възходящ ред. В противен случай алгоритъмът няма да намери верния отговор. Ако го направи, ще бъде по съвпадение.

💡 Съвет: Можете да сортирате последователността, преди да приложите двоично търсене с алгоритъм за сортиране, който отговаря на вашите нужди.

Вход и изход

Алгоритъмът (реализиран като функция) се нуждае от тези данни:

• Подредена последователност от елементи (например: списък, кортеж, низ).
• Целевият елемент, който търсим.

Той връща индекса на елемента, който търсите, ако е намерен. Ако елементът не бъде намерен, се връща -1.

Ефективност

Той е много ефективен в сравнение с Линейно търсене (търсене на елемент един по един, започвайки от първия), защото ние сме в състояние да "отхвърлим" половината от списъка на всяка стъпка.

Нека започнем да се впускаме в този алгоритъм.

🔸 Визуално разходка

Ще приложим алгоритъма за двоично търсене към този списък:

💡 Съвет: Забележете, че списъкът вече е сортиран. Той включваше индексите като визуална справка.

Цел

Искаме да намерим индекса на цялото число 67 .

Интервал

Нека се преструваме, че ние сме алгоритъмът. Как да започнем процеса?

Започваме с избирането на двете граници на интервала, в който искаме да търсим. Искаме да претърсим целия списък, затова избираме индекс 0като долна граница и индекс 5като горна граница:

Среден елемент

Сега трябва да намерим индекса на средния елемент в този интервал. Правим това, като добавяме долната и горната граница и разделяме резултата на 2, като използваме целочислено деление.

В този случай, (0 + 5)//2е 2, защото в резултат на 5/2е 2.5и целочислено деление отрязва десетичната част.

И така, средният елемент се намира в индекс 2 , а средният е числото 6 :

Сравнения

Сега трябва да започнем да сравняваме средния елемент с нашия целеви елемент, за да видим какво трябва да направим по-нататък.

Ние питаме:

Равен ли е средният елемент на елемента, който търсим?

6 == 67 # False

Не, не е така.

Затова питаме:

По-голям ли е средният елемент от елемента, който търсим?

6 > 67 # False

Не, не е така.

Така че средният елемент е по-малък от елемента, който търсим.

6 < 67 # True

Изхвърлете елементите

Тъй като списъкът вече е сортиран, това ни казва нещо изключително важно. Това ни казва, че можем да „отхвърлим“ долната половина на списъка, защото знаем, че всички елементи, които идват преди средния елемент, ще бъдат по-малки от елемента, който търсим, така че целевият ни елемент не е там.

Започнете отново - изберете границите

Какво да правим по-нататък? Изхвърлихме елементите и цикълът се повтаря отново.

Трябва да изберем границите за новия интервал (виж по-долу). Но забележете, че горната граница се запазва непокътната и се променя само долната граница.

Това е така, защото елементът, който търсим, може да бъде в горната половина на списъка. Горната граница се запазва непокътната, а долната се променя, за да „свие“ интервала до интервал, в който може да бъде намерен целевият ни елемент.

💡 Съвет: Ако средният елемент беше по-голям от елемента, който търсим, горната граница щеше да бъде променена и долната граница щеше да бъде запазена непокътната. По този начин бихме отхвърлили горната половина на списъка и бихме продължили търсенето в долната половина.

Среден елемент

Сега трябва да намерим индекса на средния елемент, като добавим долната граница към горната граница и разделим резултата на 2 с помощта на цяло число деление.

Резултатът от (3+5)//2е 4, така че средният елемент се намира в индекс,4 а средният е 67 .

Сравнения

Ние питаме:

Равен ли е средният елемент на елемента, който търсим?

67 == 67 # True

Да, така е! Така че намерихме елемента в индекс 4 . Връща се стойността 4 и алгоритъмът е завършен успешно.

💡 Съвет: Ако елементът не беше намерен, процесът щеше да продължи, докато интервалът вече не беше валиден. Ако елементът не беше намерен в целия списък, -1 щеше да бъде върнат.

Walk Разходка за кодове

Сега, когато имате визуална интуиция за това как алгоритъмът работи зад кулисите, нека се потопим в итеративното изпълнение на Python, като го анализираме ред по ред:

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

Хедър

Тук имаме заглавката на функцията:

def binary_search(data, elem):

Необходими са два аргумента:

• Подредената последователност от елементи (например: списък, кортеж или низ).
• Елементът, който искаме да намерим.

Първоначален интервал

Следващият ред задава началните долни и горни граници:

low = 0 high = len(data) - 1

Началната долна граница е индекс, 0а началната горна граница е последният индекс на последователността.

Примка

Ще повторим процеса, докато има валиден интервал, докато долната граница е по-малка или равна на горната граница.

while low <= high:

💡 Съвет: Не забравяйте, че границите са индекси.

Среден елемент

При всяка итерация трябва да намерим индекса на средния елемент. За да направите това, добавяме долната и горната граница и разделяме резултата на 2, като използваме целочислено деление.

middle = (low + high)//2

💡 Съвет: Използваме целочислено разделение, в случай че списъкът или интервалът съдържа четен брой елементи. Например, ако списъкът има 6 елемента и не използваме целочислено разделение, middleрезултатът от (0 + 5)/2който е 2.5. Индексът не може да бъде плаващ, така че ние съкращаваме десетичната част, като използваме //и избираме елемента в индекса 2.

Сравнения

С тези условни условия (вижте по-долу) ние определяме какво да правим в зависимост от стойността на средния елемент data[middle]. Сравняваме го с целевия елемент, който търсим.

if data[middle] == elem: return middle elif data[middle] > elem: high = middle - 1 else: low = middle + 1

Има три възможности:

• Ако средният елемент е равен на елемента, който търсим, връщаме индекса веднага, защото намерихме елемента.

if data[middle] == elem: return middle

• Ако средният елемент е по-голям от елемента, който търсим, ние преназначаваме горната граница, защото знаем, че целевият елемент е в долната половина на списъка.

elif data[middle] > elem: high = middle - 1

• В противен случай остава единствената опция, че средният елемент е по-малък от елемента, който търсим, затова преназначаваме долната граница, защото знаем, че целевият елемент е в горната половина на списъка.

else: low = middle + 1

Елементът не е намерен

Ако цикълът е завършен, без да се намери елементът, се връща стойността -1.

return -1

и имаме окончателно внедряване на алгоритъма за двоично търсене:

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

🔸 Специални случаи

Това са някои конкретни случаи, които може да откриете, когато започнете да работите с този алгоритъм:

Повтарящи се елементи

Ако търсеният от вас елемент се повтаря в последователността, върнатият индекс ще зависи от броя на елементите и от последователността на операциите, които алгоритъмът изпълнява върху последователността.

>>> >>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 7) 4 

Елементът не е намерен

Ако елементът не бъде намерен, се връща -1.

>>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 8) -1

Празна последователност

Ако последователността е празна, ще се върне -1.

>>> b = [] >>> binary_search(b, 8) -1

Несортирана последователност

Ако последователността е несортирана, отговорът няма да е верен. Получаването на правилния индекс е чисто съвпадение и това може да се дължи на реда на елементите в последователността и последователността на операциите, изпълнявани от алгоритъма.

Този пример връща правилния резултат:

>>> b = [5, 7, 3, 0, -9, 2, 6] >>> binary_search(b, 6) 6

Но този не:

>>> b = [5, 7, 3, 0, -9, 2, 10, 6] >>> binary_search(b, 6) -1

💡 Съвет: Помислете защо първият пример връща правилния резултат. Съвет: Чиста случайност е, че редът на елементите се случва така, че алгоритъмът да достигне правилния индекс, но процесът стъпка по стъпка оценява 0, след това 2и накрая 6. В този конкретен случай, за този конкретен елемент се намира правилният индекс, дори ако последователността не е сортирана.

🔹 По-сложен пример

Сега, когато сте по-запознати с алгоритъма и неговото изпълнение на Python, тук имаме по-сложен пример:

Искаме да намерим индекса на елемента 45 в този списък, използвайки двоично търсене:

Първа итерация

Долната и горната граници са избрани:

Избран е средният елемент ( 26 ):

Но средният елемент ( 26 ) не е елементът, който търсим, той е по-малък от 45 :

Второ повторение

Така че можем да отхвърлим всички елементи, които са по-малки от средния елемент и да изберем нови граници. Новата долна граница ( 27 ) е елементът, разположен непосредствено вдясно от предишния среден елемент:

💡 Съвет: Не забравяйте, че списъкът вече е сортиран.

Избран е новият среден елемент ( 30 ):

Средният елемент ( 30 ) не е елементът, който търсим, той е по-малък от 45 :

Трета итерация

Можем да изхвърлим елементите, които са по-малки или равни на 30, които вече не са били изхвърлени. Долната граница се актуализира до 32 :

Тук имаме интересен случай: средният елемент е една от границите на текущия интервал, защото (7+8)//2е 7.

Средният елемент ( 32 ) не е елементът, който търсим ( 45 ), той е по-малък.

Четвърто повторение

Можем да изхвърлим елементите, които са по-малки или равни на 32, които вече не са били изхвърлени.

Тук имаме още един много интересен случай: интервалът има само един елемент.

💡 Съвет: Този интервал е валиден, защото написахме това условие while high <= low:, което включва интервали, при които индексът на долната граница е равен на индекса на горната граница.

Средният елемент е единственият елемент в интервала, защото (8+8)//2е 8, така че индексът на средния елемент е 8, а средният елемент е 45 .

Сега средният елемент е елементът, който търсим, 45 :

Така се връща стойността 8 (индексът):

>>> binary_search([1, 3, 7, 15, 26, 27, 30, 32, 45], 45) 8

🔸 Допълнителна практика

Ако искате да имате допълнителна практика с този алгоритъм, опитайте да обясните как работи алгоритъмът зад кулисите, когато е приложен към този списък, за да намерите цялото число 90 :

[5, 8, 15, 26, 38, 56]

• Какво се случва стъпка по стъпка?
• Каква стойност се връща?
• Намерен ли е елементът?

Надявам се наистина да сте харесали статията ми и сте я намерили за полезна. Сега можете да внедрите алгоритъма за двоично търсене в Python. Вижте моя онлайн курс „Алгоритми за търсене и сортиране на Python: Практически подход“. Последвай ме в Туйтър. ⭐️