Cos'è la ricerca binaria?

Una ricerca binaria è un algoritmo di ricerca utilizzato per cercare elementi target in un contenitore in cui gli elementi devono essere disposti in ordine crescente. Generalmente, la ricerca binaria viene utilizzata per cercare il numero dell'indice dell'elemento target in un array ordinato.

La ricerca binaria utilizza l'approccio di divisione e conquista, in cui divide l'array in parti uguali fino a quando non trova l'elemento target.

Un algoritmo di ricerca binaria è implementato iterativo e una dichiarazione ricorsiva. La ricerca binaria è più efficiente e più veloce rispetto alla ricerca lineare.

Algoritmo di ricerca binaria

1. Ordina e disporre gli elementi nell'array arr in ordine crescente.
2. Gli algoritmi confrontano l'elemento centrale N con l'elemento target bersaglio.
3. L'algoritmo restituisce l'indice di posizione dell'elemento medio se l'elemento target risulta essere uguale all'elemento centrale,
4. L'algoritmo cerca la metà inferiore dell'array se l'elemento target è inferiore all'elemento medio.
5. L'algoritmo cerca la metà superiore dell'array se l'elemento target è maggiore dell'elemento medio.
6. L'algoritmo continua a ripetere il 4 ° e il 5 ° passaggio fino a quando la lunghezza dell'array diventa uno o meno di 1.

Alla fine, il valore dell'indice dell'elemento viene restituito o l'elemento non esiste nell'array.

Pseudocodi di ricerca binaria

Iterativo

funzione binary_search (arr, n, target) è
a sinistra: = 0
a destra: = n - 1
mentre a sinistra ≤ a destra fare
Medio: = pavimento ((sinistra + a destra) / 2)
Se Arr [Middle] Target allora
a destra: = medio - 1
altro:
ritorno in mezzo
restituire senza successo

Ricorsivo

funzione binary_search (arr, sinistra, destra, target) è
Se a destra> = a sinistra
Middle = (sinistra+a destra) // 2
Se arr [Middle] == Target
ritorno in mezzo
altrimenti se arr [Middle]> Target
return binary_search (arr, basso, metà 1, target)
altro
return binary_search (arr, mid+1, a destra, target)
altro
restituire senza successo

Implementa la ricerca binaria in Python

Iterativo
Nell'approccio iterativo, utilizziamo i loop per implementare la ricerca binaria.

def binary_search (arr, n, target):
a sinistra = 0
a destra = n-1
Middle = 0
mentre è a sinistra<=right:
Middle = (destra+sinistra) // 2
#Se l'elemento centrale è uguale all'elemento target
Se arr [Middle] == Target:
ritorno in mezzo
# se l'elemento target è maggiore dell'elemento medio
Elif arr [Middle]< target:
a sinistra = medio+1
# se l'elemento target è inferiore all'elemento medio
altro:
a destra = Middle-1
# se l'elemento target non è presente nell'array
restituzione -1
Se __Name__ == '__main__':
# Array ordinato
Sorted_arr = [0,4,7,10,14,23,45,47,53]
# lunghezza dell'array
n = len (seled_arr)
#element da cercare
Target = 47
posizione = binary_search (seled_arr, n, target)
se posizione != -1:
print (f "elemento target presente su indice position")
altro:
print (f "Element target non si presenta in array")

Produzione

Elemento 47 presente all'indice 7

Ricorsivo
In ricorsivo invece di usare loop, continuiamo a chiamare la funzione ancora e ancora fino a quando la condizione di base non viene soddisfatta

def binary_search (arr, sinistra, destra, target):
#CONDIZIONE BASE
Se RightTarget:
return binary_search (arr, sinistra, mezzo-1, target)
#Se l'elemento target è più piccolo dell'elemento medio
altro:
return binary_search (arr, mezzo+1, a destra, target)
Se __Name__ == '__main__':
# Array ordinato
Sorted_arr = [0,4,7,10,14,23,45,47,53]
a sinistra = 0
a destra = len (seled_arr) -1
#element da cercare
Target = 47
posizione = binary_search (seled_arr, sinistra, destra, target)
se posizione != -1:
print (f "elemento target presente su indice position")
altro:
print (f "Element target non si presenta in array")

Produzione

L'elemento 90 non è presente nell'array

Complessità

La ricerca binaria ha una complessità temporale di O (log n), dove N è il numero di elementi presenti nell'array.

La ricerca binaria ha una complessità spaziale di O (1) perché, nell'algoritmo, stiamo eseguendo la ricerca sul posto.

Conclusione

La ricerca binaria è uno dei migliori ed efficienti algoritmi di ricerca. Anche la complessità del tempo e dello spazio della ricerca binaria è molto bassa; L'unico prerequisito di ricerca binaria è che l'array di input dovrebbe essere ordinato in ordine crescente.