Abbiamo diviso una raccolta di elementi in due metà nella ricerca binaria per ridurre il numero di confronti diretti necessari per scoprire un elemento. Tuttavia, c'è un requisito: gli elementi dell'array devono essere ordinati in anticipo.
Ricerca binaria
IL Ricerca binaria Il metodo individua l'indice di un determinato membro dell'elenco. È tra gli algoritmi più popolari e più veloci. Affinché la procedura di ricerca binaria funzioni, le voci nell'elenco devono essere ordinate.
Ricerca binaria è una tecnica di ricerca più efficiente per individuare l'indice di un elemento rispetto a Ricerca lineare poiché non dobbiamo esaminare ogni indice dell'elenco.
L'intero funzionamento dell'algoritmo di ricerca binaria può essere riassunto nei seguenti passaggi:
- Individua l'elemento centrale nell'array ordinato.
- Effettuare un confronto tra l'elemento da localizzare e l'elemento centrale.
- Se quell'elemento è uguale all'elemento centrale della lista data, viene restituito l'indice dell'elemento centrale. Altrimenti, l'algoritmo confronterà l'elemento con l'elemento al centro.
- Ora, se l'elemento da localizzare è maggiore dell'elemento centrale della lista, verrà confrontato con la metà destra della lista, cioè con gli elementi dopo l'indice centrale.
- Oppure, se l'elemento è inferiore all'elemento al centro dell'elenco, verrà confrontato solo con la metà sinistra dell'elenco, ovvero con gli elementi prima dell'indice centrale.
Ricerca binaria ricorsiva
La ricerca binaria implica la divisione continua dell'intervallo di ricerca in 2 parti uguali per scoprire un elemento in un array ordinato, mentre la ricerca binaria ricorrente comporta la suddivisione dell'intera procedura di ricerca binaria in elementi più piccoli. Una ricerca binaria ricorsiva è la risposta ricorsiva a una ricerca binaria.
Di seguito sono riportate le caratteristiche che le soluzioni all-recursive devono soddisfare:
- Per un approccio ricorsivo è necessario un caso base.
- Deve esserci un caso di test ricorsivo in un approccio ricorsivo.
- Un approccio ricorsivo deve avvicinarsi al caso base.
La suddivisione più bassa di un problema complicato è rappresentata dal caso base, che è un caso finale. Pertanto, per eseguire la ricerca binaria con il metodo ricorsivo, il nostro algoritmo deve contenere un caso base e un caso ricorsivo, con il caso ricorsivo che procede al caso base. Altrimenti il processo non finirebbe mai e si tradurrebbe in un ciclo infinito.
La tecnica di ricerca binaria riduce il tempo necessario per trovare un elemento specifico all'interno di un array ordinato. Il metodo di ricerca binaria viene spesso implementato in modo iterativo, ma possiamo anche implementarlo in modo ricorsivo suddividendolo in parti più piccole.
Codice
#defining a function to execute Binary Search on any given sorted list L. #start is the lowest index of the list being checked at any given time. #end is the highest index of the list being checked at any given time. #item is the item to be searched in the list. def binary_search(L, start, end, item): if end >= start: middle = (start + end) // 2 if L[middle] == item: return middle #middle element is the item to be located #if middle item is greater than the item to be searched, left side of the list will be searched elif L[middle] > item: #starting index will be same but ending index will be the middle of the main list i.e. left half of the list is given in function. return binary_search(L, start, middle - 1, item) else: #if middle item is smaller than the item to be searched, new starting index will be middle of the list i.e. right half of the list. return binary_search(L, middle + 1, end, item) else: #if element is not present in the list return -1 #Drivers code my_list = [ 2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22 ] element_to_search = 6 print('The given list is') print(my_list) index_of_element = binary_search(my_list, 0, len(my_list)-1, element_to_search) if index_of_element != -1: print('Element searched is found at the index ', str(index_of_element), 'of given list') else: print('Element searched is not found in the given list!')
Produzione:
The given list is [2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22] Element searched is found at the index 2 of given list
La ricorsione è una tecnica di programmazione e risoluzione dei problemi estremamente potente. Possiamo usarlo per valutare ed eseguire una varietà di algoritmi, che vanno da semplici problemi iterativi a complicati problemi di backtracking. In questo tutorial, abbiamo esaminato l'utilizzo del linguaggio Python per creare il metodo di ricerca binaria ricorsiva.