Căutare binară în Python: o introducere vizuală

Bine ati venit

În acest articol, veți afla cum funcționează algoritmul Binary Search în culise și cum îl puteți implementa în Python.

În special, veți învăța:

• Cum funcționează algoritmul din culise pentru a găsi un element țintă.
• Cum funcționează implementarea sa Python linie cu linie.
• De ce este un algoritm foarte eficient în comparație cu Căutarea liniară.
• Avantajele și cerințele sale.

Sa incepem! ✨

???? Introducere în Căutare binară

Acest algoritm este utilizat pentru a găsi un element într-o secvență ordonată (de exemplu: o listă, un tuplu sau un șir).

Cerințe

Pentru a aplica algoritmul Binary Search unei secvențe, secvența trebuie să fie deja sortată în ordine crescătoare. În caz contrar, algoritmul nu va găsi răspunsul corect. Dacă o va face, va fi prin pură coincidență.

???? Sfat: Puteți sorta secvența înainte de a aplica Binary Search cu un algoritm de sortare care să răspundă nevoilor dvs.

Intrare și ieșire

Algoritmul (implementat ca funcție) are nevoie de aceste date:

• O secvență ordonată de elemente (de exemplu: listă, tuplu, șir).
• Elementul țintă pe care îl căutăm.

Se întoarce index a elementului pe care îl căutați dacă este găsit. Dacă elementul nu este găsit, se returnează -1.

Eficienţă

Este foarte eficient în comparație cu Căutarea liniară (căutarea unui element unul câte unul, începând cu primul), deoarece suntem capabili să „aruncăm” jumătate din listă la fiecare pas.

Să începem să ne scufundăm în acest algoritm.

???? Procedură vizuală

Vom aplica algoritmul Binary Search la această listă:

???? Sfat: Observați că lista este deja sortată. Acesta a inclus indicii ca referință vizuală.

Poartă

Vrem să găsim indicele întregului 67.

Interval

Să ne prefacem că suntem algoritmul. Cum începem procesul?

Începem prin selectarea celor două limite ale intervalului în care dorim să căutăm. Vrem să căutăm întreaga listă, așa că selectăm indexul 0 ca limita inferioară și index 5 ca limita superioară:

Element de mijloc

Acum trebuie să găsim indicele elementului de mijloc în acest interval. Facem acest lucru adăugând limita inferioară și limita superioară și împărțind rezultatul la 2 folosind împărțirea întreagă.

În acest caz, (0 + 5)//2 este 2 deoarece rezultatul 5/2 este 2.5 iar diviziunea întreagă trunchiază partea zecimală.

Deci elementul de mijloc este situat la indicele 2, iar elementul de mijloc este numărul 6:

Comparații

Acum trebuie să începem să comparăm elementul de mijloc cu elementul nostru țintă pentru a vedea ce trebuie să facem în continuare.

Noi intrebam:
Este elementul de mijloc egal cu elementul pe care îl căutăm?

6 == 67 # False

Nu, nu este.

Așa că întrebăm:
Este elementul de mijloc mai mare decât elementul pe care îl căutăm?

6 > 67 # False

Nu, nu este.

Asa de elementul de mijloc este mai mic decât elementul pe care îl căutăm.

6 < 67 # True

Eliminați elementele

Întrucât lista este deja sortată, acest lucru ne spune ceva extrem de important. Ne spune că putem „arunca” jumătatea inferioară a listei, deoarece știm că toate elementele care vin înainte de elementul de mijloc vor fi mai mici decât elementul pe care îl căutăm, astfel încât elementul nostru țintă nu este acolo.

Începeți din nou – Alegeți limitele

Ce facem în continuare? Am eliminat elementele și ciclul se repetă din nou.

Trebuie să alegem limitele pentru noul interval (a se vedea mai jos). Dar observați că limita superioară este păstrată intactă și numai limita inferioară este modificată.

Acest lucru se datorează faptului că elementul pe care îl căutăm ar putea fi în jumătatea superioară a listei. Limita superioară este păstrată intactă și limita inferioară este schimbată pentru a „micșora” intervalul la un interval în care ar putea fi găsit elementul nostru țintă.

???? Bacsis: Dacă elementul din mijloc ar fi fost mai mare decât elementul pe care îl căutăm, limita superioară ar fi fost schimbată și limita inferioară ar fi fost păstrată intactă. În acest fel, am renunța la jumătatea superioară a listei și am continua să căutăm în jumătatea inferioară.

Element de mijloc

Acum trebuie să găsim indicele elementului de mijloc adăugând limita inferioară la limita superioară și împărțind rezultatul la 2 folosind diviziunea întreagă.

Rezultatul (3+5)//2 este 4, deci elementul de mijloc este situat la index 4 iar elementul de mijloc este 67.

Comparații

Noi intrebam:
Este elementul de mijloc egal cu elementul pe care îl căutăm?

67 == 67 # True

Da, este! Deci, am găsit elementul la index 4. Se returnează valoarea 4 și algoritmul a fost finalizat cu succes.

???? Bacsis: Dacă elementul nu ar fi fost găsit, procesul ar fi continuat până când intervalul nu va mai fi valid. Dacă elementul nu ar fi fost găsit în întreaga listă, -1 ar fi fost returnat.

???? Cod pasaj

Acum, că aveți o intuiție vizuală a modului în care algoritmul funcționează în culise, să ne scufundăm în implementarea iterativă Python analizând-o linie cu linie:

def binary_search(data, elem):

    low = 0
    high = len(data) - 1

    while low <= high:
      
        middle = (low + high)//2
       
        if data[middle] == elem:
            return middle
        elif data[middle] > elem:
            high = middle - 1
        else:
            low = middle + 1

    return -1

Antet

Aici avem antetul funcției:

def binary_search(data, elem):

Este nevoie de două argumente:

• Secvența ordonată a elementelor (de exemplu: listă, tuplu sau șir).
• Elementul pe care vrem să-l găsim.

Interval inițial

Următoarea linie stabilește limitele inferioare și superioare inițiale:

low = 0
high = len(data) - 1

Limita inferioară inițială este index 0 iar limita superioară inițială este ultimul index al secvenței.

Buclă

Vom repeta procesul în timp ce există un interval valid, în timp ce limita inferioară este mai mică sau egală cu limita superioară.

while low <= high:

???? Bacsis: Amintiți-vă că limitele sunt indicii.

Element de mijloc

La fiecare iterație, trebuie să găsim indexul elementului de mijloc. Pentru a face acest lucru, adăugăm limitele inferioară și superioară și împărțim rezultatul la 2 folosind divizarea întreagă.

middle = (low + high)//2

???? Bacsis: Folosim divizarea numărului întreg în cazul în care lista sau intervalul conțin un număr par de elemente. De exemplu, dacă lista avea 6 elemente și nu am folosit diviziuni întregi, middle ar fi rezultatul (0 + 5)/2 care este 2.5. Un index nu poate fi un float, așa că tăiem porțiunea zecimală folosind // și selectați elementul la index 2.

Comparații

Cu aceste condiționale (a se vedea mai jos), determinăm ce să facem în funcție de valoarea elementului de mijloc data[middle]. O comparăm cu elementul țintă pe care îl căutăm.

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

Există trei opțiuni:

• Dacă elementul de mijloc este egal cu elementul pe care îl căutăm, returnăm indexul imediat pentru că am găsit elementul.

if data[middle] == elem:
    return middle

• Dacă elementul din mijloc este mai mare decât elementul pe care îl căutăm, reasignăm limita superioară pentru că știm că elementul țintă se află în jumătatea inferioară a listei.

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

• Altfel, singura opțiune rămasă este că elementul din mijloc este mai mic decât elementul pe care îl căutăm, așa că redistribuim limita inferioară, deoarece știm că elementul țintă se află în jumătatea superioară a listei.

else:
    low = middle + 1

Elementul nu a fost găsit

Dacă bucla este finalizată fără a găsi elementul, se returnează valoarea -1.

return -1

și avem implementarea finală a algoritmului de căutare binară:

def binary_search(data, elem):

    low = 0
    high = len(data) - 1

    while low <= high:
      
        middle = (low + high)//2
       
        if data[middle] == elem:
            return middle
        elif data[middle] > elem:
            high = middle - 1
        else:
            low = middle + 1

    return -1

???? Cazuri speciale

Acestea sunt câteva cazuri particulare pe care le puteți găsi atunci când începeți să lucrați cu acest algoritm:

Elemente repetate

Dacă elementul pe care îl căutați se repetă în secvență, indexul returnat va depinde de numărul de elemente și de secvența de operații pe care algoritmul le efectuează asupra secvenței.

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

Elementul nu a fost găsit

Dacă elementul nu este găsit, se returnează -1.

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

Secvență goală

Dacă secvența este goală, -1 va fi returnat.

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

Secvență nesortată

Dacă secvența este nesortată, răspunsul nu va fi corect. Obținerea indexului corect este pură coincidență și s-ar putea datora ordinii elementelor din secvență și succesiunii operațiilor efectuate de algoritm.

Acest exemplu returnează rezultatul corect:

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

Dar acesta nu:

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

???? Bacsis: Gândiți-vă de ce primul exemplu returnează rezultatul corect. Sugestie: este pură coincidență faptul că ordinea elementelor se întâmplă pentru a face algoritmul să atingă indicele corect, dar procesul pas cu pas evaluează 0, atunci 2, și, în sfârșit 6. În acest caz particular, pentru acest element particular, indexul corect este găsit chiar dacă secvența nu este sortată.

???? Un exemplu mai complex

Acum, că sunteți mai familiarizați cu algoritmul și implementarea lui Python, aici avem un exemplu mai complex:

Vrem să găsim indexul elementului 45 în această listă folosind Căutare binară:

Prima iterație

Limitele inferioară și superioară sunt selectate:

Elementul de mijloc (26) este selectat:

Dar elementul de mijloc (26) nu este elementul pe care îl căutăm, este mai mic decât 45:

A doua iterație

Deci, putem arunca toate elementele care sunt mai mici decât elementul din mijloc și putem selecta limite noi. Noua limită inferioară (27) este elementul situat imediat în dreapta elementului de mijloc anterior:

???? Bacsis: Amintiți-vă că lista este deja sortată.

Noul element de mijloc (30) este selectat:

Elementul de mijloc (30) nu este elementul pe care îl căutăm, este mai mic decât 45:

A treia iterație

Putem arunca elementele care sunt mai mici sau egale cu 30 care nu au fost deja aruncate. Limita inferioară este actualizată la 32:

Aici avem un caz interesant: elementul de mijloc este una dintre limitele intervalului curent deoarece (7+8)//2 este 7.

Elementul de mijloc (32) nu este elementul pe care îl căutăm (45), este mai mic.

A patra iterație

Putem arunca elementele care sunt mai mici sau egale cu 32 care nu au fost deja aruncate.

Aici avem un alt caz foarte interesant: intervalul are doar un element.

???? Bacsis: Acest interval este valid deoarece am scris această condiție while high <= low: , care include intervale în care indicele limitei inferioare este egal cu indicele limitei superioare.

Elementul de mijloc este singurul element din interval deoarece (8+8)//2 este 8, deci indicele elementului de mijloc este 8 iar elementul de mijloc este 45.

Acum elementul de mijloc este elementul pe care îl căutăm, 45:

Deci valoarea 8 (indexul) este returnat:

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

???? Practică suplimentară

Dacă doriți să aveți o practică suplimentară cu acest algoritm, încercați să explicați cum funcționează algoritmul din culise atunci când este aplicat acestei liste pentru a găsi numărul întreg 90:

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

• Ce se întâmplă pas cu pas?
• Ce valoare este returnată?
• Se găsește elementul?

Sper cu adevărat că ți-a plăcut articolul meu și l-ai găsit util. Acum puteți implementa algoritmul de căutare binară în Python. Vezi cursul meu online “Algoritmi de căutare și sortare Python: o abordare practică“. Urmează-mă Stare de nervozitate. ⭐️