Program Python pentru căutare binară (recursiv și iterativ)
Pe scurt, acest algoritm de căutare profită de o colecție de elemente care este deja sortată ignorând jumătate dintre elemente după o singură comparație.
- Comparați x cu elementul din mijloc.
- Dacă x se potrivește cu elementul din mijloc, returnăm indicele mijlociu.
- În caz contrar, dacă x este mai mare decât elementul mijlociu, atunci x poate fi situat doar în jumătatea din dreapta (mai mare) după elementul mijlociu. Apoi aplicăm algoritmul din nou pentru jumătatea dreaptă.
- Altfel, dacă x este mai mic, ținta x trebuie să se afle în jumătatea stângă (inferioară). Deci aplicăm algoritmul pentru jumătatea stângă.
Program Python pentru căutare binară folosind recursiv
Python3
# Python 3 program for recursive binary search.> # Modifications needed for the older Python 2 are found in comments.> # Returns index of x in arr if present, else -1> def> binary_search(arr, low, high, x):> > # Check base case> > if> high>>>> ,> str> (result))> else> :> > print> (> 'Element is not present in array'> )> |
Ieșire
Element is present at index 3
Complexitatea timpului : O(log n)
Spațiu auxiliar : O(logn) [NOTĂ: recursiunea creează stiva de apeluri]
Program Python pentru căutare binară folosind iterativ
Python3
# Iterative Binary Search Function> # It returns index of x in given array arr if present,> # else returns -1> def> binary_search(arr, x):> > low> => 0> > high> => len> (arr)> -> 1> > mid> => 0> > while> low <> => high:> > mid> => (high> +> low)> /> /> 2> > # If x is greater, ignore left half> > if> arr[mid] low = mid + 1 # If x is smaller, ignore right half elif arr[mid]>x: high = mid - 1 # înseamnă că x este prezent la mijloc else: return mid # Dacă ajungem aici, atunci elementul nu a fost prezent return -1 # Test matrice arr = [ 2, 3, 4, 10, 40 ] x = 10 # Rezultatul apelului de funcție = binary_search(arr, x) if result != -1: print('Elementul este prezent la index', str(rezultat)) else: print('Elementul nu este prezent în matrice ')>>> |
>
Spațiu auxiliar : O(1) Programul Python pentru căutare binară Folosind modulul încorporat bisect
Abordare pas cu pas:
- Codul importă modulul bisect care oferă suport pentru căutarea binară.
- Funcția binary_search_bisect() este definită care ia o matrice arr și elementul pentru a căuta x ca intrări.
- Funcția apelează funcția bisect_left() a modulului bisect care găsește poziția elementului în matricea sortată arr unde x ar trebui să fie inserat pentru a menține ordinea sortată. Dacă elementul este deja prezent în matrice, această funcție își va întoarce poziția.
- Funcția verifică apoi dacă indexul returnat i se află în intervalul matricei și dacă elementul de la acel index este egal cu x.
- Dacă condiția este adevărată, atunci funcția returnează indexul i ca poziție a elementului în tablou.
- Dacă condiția este falsă, atunci funcția returnează -1 indicând faptul că elementul nu este prezent în matrice.
- Codul definește apoi o matrice arr și un element x de căutat.
- Funcția binary_search_bisect() este apelată cu arr și x ca intrări, iar rezultatul returnat este stocat în variabila rezultat.
- Codul verifică apoi dacă rezultatul nu este egal cu -1, indicând faptul că elementul este prezent în matrice. Dacă este adevărat, se tipărește poziția elementului în matrice.
- Dacă rezultatul este egal cu -1, atunci codul afișează un mesaj că elementul nu este prezent în matrice.
Python3
import>bisect>>def>binary_search_bisect(arr, x):>>i>=>bisect.bisect_left(arr, x)>>if>i !>=>len>(arr)>and>arr[i]>=>=>x:>>return>i>>else>:>>return>->1>>># Test array>arr>=>[>2>,>3>,>4>,>10>,>40>]>x>=>10>># Function call>result>=>binary_search_bisect(arr, x)>>if>result !>=>->1>:>>print>(>'Element is present at index'>,>str>(result))>else>:>>print>(>'Element is not present in array'>)>
Ieșire
Element is present at index 3Complexitatea timpului : O(log n)
Spațiu auxiliar : O(1)
