Ricerca binaria di Python
Una ricerca binaria è un modo per trovare un determinato elemento all'interno di un elenco. Immaginiamo che abbiamo un elenco di diecimila elementi e dobbiamo trovare la posizione dell'indice di una singola voce. Possiamo trovare rapidamente la posizione dell'indice di un elemento usando la tecnica di ricerca binaria. Esistono altri algoritmi di ricerca, ma i più ampiamente impiegati è una ricerca binaria. Ordina prima gli oggetti se non sono già stati ordinati.
Gli approcci ricorsivi e iterativi dell'algoritmo di ricerca binaria possono essere utilizzati per trovare la posizione dell'elemento. La strategia ricorsiva viene utilizzata dopo l'approccio di divisione e conquista. In questo modo, una funzione viene eseguita fino a quando non trova un elemento nell'elenco. Per scoprire la posizione dell'indice di un elemento, la tecnica iterativa ripete ripetutamente una serie di parole. Questo processo è realizzato utilizzando il ciclo while. Poiché non dobbiamo cercare ogni indice dell'elenco, la ricerca binaria è più efficiente della ricerca lineare.
Cominciamo con una comprensione di base della ricerca binaria.
Esempio 1:
Innanzitutto, utilizziamo l'approccio iterativo per implementare una ricerca binaria. Passare attraverso l'elenco, ripetendo una sequenza di dichiarazioni. Continueremo a cercare il valore centrale fino a quando non lo troveremo.
Questa è un'implementazione di Python dell'approccio della funzione di ricerca binaria iterativa. Se 'Search_num' è presente nell'elenco indicato, ne restituisce uno; Altrimenti, dà -1. Abbiamo costruito la funzione binaria di ricerca () in questo programma, che accetta due argomenti: un elenco da ordinare e un numero da cercare. Abbiamo impostato due variabili per tenere traccia dei valori più bassi e migliori dell'elenco. Il basso ha un valore iniziale di 0, il massimo ha un valore di len (list1) - 1 e il mezzo ha un valore di 0. Il ciclo while viene quindi scritto con il vincolo che il più basso è uguale ed è più piccolo del più alto. Il ciclo while iterirà se il numero non è stato ancora trovato. Il punto medio si trova nel ciclo while. Quindi abbiniamo il valore dell'indice al numero che stavamo cercando. Se il valore dell'indice medio è inferiore a "Num di ricerca", lo assegniamo e aumentiamo il valore dell'indice medio di uno. Il focus della ricerca cambia a sinistra. Imposta il valore medio al massimo se è alto. Restituire a metà se il "search_num" è uguale al valore medio. Questo continuerà fino a quando il basso e il massimo non saranno uguali e il basso è più piccolo del massimo. Se arriviamo alla fine della funzione, sappiamo che l'elemento non è nell'elenco. Alla funzione invocazione, torniamo -1.
def binary_search (uno, search_num):basso = 0
alto = len (uno) - 1
Mid = 0
mentre è basso <= high:
mid = (alto + basso) // 2
Se uno [Mid] Search_num:
alto = Mid - 1
altro:
ritorno a metà
restituzione -1
uno = [19, 23, 43, 56, 65, 71, 80]
Search_num = 43
output = binary_search (uno, search_num)
Se output != -1:
Print ("Element Is at Index", STR (output))
altro:
Stampa ("L'elemento non è disponibile nell'elenco")
Qui puoi vedere che il numero richiesto viene trovato nella posizione dell'indice 2.
Esempio 2:
Diamo un'occhiata all'approccio di ricerca binaria ricorsiva. L'approccio di ricorsione può essere utilizzato nella ricerca binaria. Faremo una funzione ricorsiva che si chiama fino a quando la condizione non sarà soddisfatta. Il programma precedente è simile a quello precedente. Sono state dichiarate una funzione ricorsiva, così come la sua condizione di base. Calcoliamo il numero centrale come abbiamo fatto nel programma precedente. Per continuare con la ricerca binaria, abbiamo usato l'istruzione IF. Verrà restituito se il valore medio è equivalente al numero che stiamo cercando. Se il valore medio è inferiore al valore, lo aumentiamo di uno e lo assegniamo a basso utilizzando la nostra funzione di ricerca binaria ricorsiva (). Abbiamo scritto il nostro programma principale nell'ultima sezione. La procedura di ricerca binaria () ora richiede 2 parametri, che è l'unica modifica dal programma precedente. L'incapacità della funzione ricorsiva di assegnare valori iniziali al basso, alto e medio è la ragione dietro questo. Il valore per quelle variabili verrà ripristinato ogni volta che viene chiamata la ricorsione.
def binary_search (uno, basso, alto, search_num):Se Low Search_num:
return binary_search (uno, basso, metà - 1, search_num)
altro:
return binary_search (uno, metà + 1, alto, search_num)
altro:
restituzione -1
uno = [19, 23, 43, 56, 65, 71, 80]
Search_num = 65
output = binary_search (one, 0, len (one) -1, search_num)
Se Search_num != -1:
Print ("Element Is at Index", STR (output))
altro:
Stampa ("L'elemento non è disponibile nell'elenco")
Il valore richiesto è all'indice 4, come puoi vedere nella seguente immagine.
Esempio 3:
Un altro esempio di una tecnica di ricerca binaria, comunemente noto come un algoritmo di ricerca a metà intervallo, viene utilizzato per individuare un valore target all'interno di un array ordinato. Questo programma restituisce vero se il numero si trova nell'elenco.
def binary_search (my_list, search_num):uno = 0
finale = len (my_list) -1
trovato = false
mentre (uno<=final and not found):
mid = (uno + finale) // 2
Se my_list [mid] == search_num:
trovato = vero
altro:
Se Search_num
altro:
One = Mid + 1
ritorno trovato
Stampa (binary_search ([1,2,3,4,5], 3))
print (binary_search ([11,22,33,44,55], 5))
Di seguito è riportato l'output.
Conclusione:
L'approccio più efficace e rapido alla ricerca di una voce in un elenco è utilizzare un algoritmo di ricerca binaria. Salta sull'analogia insignificante. Come dice il nome, la ricerca è divisa in due pezzi. Si concentra sul lato dell'elenco più vicino al numero che stiamo cercando. Nella situazione migliore, la complessità dell'algoritmo di ricerca binaria è O (1). Ciò si verifica quando l'elemento che stiamo cercando appare nel primo confronto. La complessità del caso peggiore e medio della ricerca binaria è O (LOG). Il numero totale di ricerche richieste per individuare l'elemento determina questo. Sono stati discussi diversi approcci per determinare la posizione dell'indice di un determinato numero.