Questo tutorial imparerà come applicare un algoritmo di ricerca binaria utilizzando Python per trovare la posizione dell'indice di un elemento nell'elenco fornito.

introduzione

Una ricerca binaria è un algoritmo per trovare un particolare elemento nell'elenco. Supponiamo di avere un elenco di migliaia di elementi e di dover ottenere la posizione dell'indice di un particolare elemento. Possiamo trovare la posizione dell'indice dell'elemento molto velocemente utilizzando l'algoritmo di ricerca binaria.

Esistono molti algoritmi di ricerca, ma tra questi il ​​più popolare è la ricerca binaria.

Gli elementi nell'elenco devono essere ordinati per applicare l'algoritmo di ricerca binaria. Se gli elementi non sono ordinati, ordinali prima.

Comprendiamo il concetto di ricerca binaria.

Concetto di ricerca binaria

Nell'algoritmo di ricerca binaria, possiamo trovare la posizione dell'elemento utilizzando i seguenti metodi.

• Metodo ricorsivo
• Metodo iterativo

Alla tecnica dell’approccio “divide et impera” segue il metodo ricorsivo. In questo metodo, una funzione viene richiamata più e più volte finché non trova un elemento nell'elenco.

Una serie di istruzioni viene ripetuta più volte per trovare la posizione di indice di un elemento nel metodo iterativo. IL Mentre loop viene utilizzato per eseguire questa attività.

tuple di ordinamento Python

La ricerca binaria è più efficace della ricerca lineare perché non è necessario cercare in ogni indice dell'elenco. L'elenco deve essere ordinato per ottenere l'algoritmo di ricerca binaria.

Vediamo un'implementazione passo passo della ricerca binaria.

Abbiamo un elenco ordinato di elementi e stiamo cercando la posizione dell'indice 45.

[12, 24, 32, 39, 45, 50, 54]

Quindi, stiamo impostando due puntatori nel nostro elenco. Un puntatore viene utilizzato per denotare il valore più piccolo chiamato Basso e il secondo puntatore viene utilizzato per denotare il valore più alto chiamato alto .

esempio di albero di ricerca binario

Successivamente, calcoliamo il valore di mezzo elemento nell'array.

 mid = (low+high)/2 Here, the low is 0 and the high is 7. mid = (0+7)/2 mid = 3 (Integer) 

Ora confronteremo l'elemento cercato con il valore dell'indice medio. In questo caso, 32 non è uguale a Quattro cinque. Quindi dobbiamo fare un ulteriore confronto per trovare l'elemento.

Se il numero che stiamo cercando è uguale a mid. Poi ritorna metà altrimenti passare al confronto ulteriore.

Il numero da cercare è maggiore di mezzo numero, confrontiamo il N con l'elemento centrale degli elementi sul lato destro di metà e impostare un valore basso su basso = medio + 1.

Altrimenti confronta il N con il elemento centrale degli elementi sul lato sinistro di metà e impostare alto A alto = medio - 1.

Ripetere finché non viene trovato il numero che stiamo cercando.

Implementa una ricerca binaria in Python

Per prima cosa implementiamo una ricerca binaria con il metodo iterativo. Ripeteremo una serie di istruzioni e itereremo ogni elemento dell'elenco. Troveremo il valore medio fino al completamento della ricerca.

lista collegata

Comprendiamo il seguente programma del metodo iterativo.

Implementazione di Python

 # Iterative Binary Search Function method Python Implementation # It returns index of n in given list1 if present, # else returns -1 def binary_search(list1, n): low = 0 high = len(list1) - 1 mid = 0 while low <= 1 2 high: # for get integer result mid="(high" + low) check if n is present at list1[mid] n: high="mid" - smaller, compared to the left of else: return element was not in list, -1 initial list1 24, 32, 39, 45, 50, 54] function call n) !="-1:" print('element index', str(result)) list1') < pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 4 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above program -</p> <ul> <li>We have created a function called <strong>binary_search()</strong> function which takes two arguments - a list to sorted and a number to be searched.</li> <li>We have declared two variables to store the lowest and highest values in the list. The low is assigned initial value to 0, <strong>high</strong> to <strong>len(list1)</strong> - 1 and mid as 0.</li> <li>Next, we have declared the <strong>while</strong> loop with the condition that the <strong>lowest</strong> is equal and smaller than the <strong>highest</strong> The while loop will iterate if the number has not been found yet.</li> <li>In the while loop, we find the mid value and compare the index value to the number we are searching for.</li> <li>If the value of the mid-index is smaller than <strong>n</strong> , we increase the mid value by 1 and assign it to The search moves to the left side.</li> <li>Otherwise, decrease the mid value and assign it to the <strong>high</strong> . The search moves to the right side.</li> <li>If the n is equal to the mid value then return <strong>mid</strong> .</li> <li>This will happen until the <strong>low</strong> is equal and smaller than the <strong>high</strong> .</li> <li>If we reach at the end of the function, then the element is not present in the list. We return -1 to the calling function.</li> </ul> <p>Let&apos;s understand the recursive method of binary search.</p> <h2>Recursive Binary Search</h2> <p>The recursion method can be used in the binary search. In this, we will define a recursive function that keeps calling itself until it meets the condition.</p> <p>Let&apos;s understand the above program using the recursive function.</p> <h3>Python Program</h3> <pre> # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print(&apos;Element is present at index&apos;, str(res)) else: print(&apos;Element is not present in list1&apos;) </pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 2 </pre> <p> <strong>Explanation</strong> </p> <p>The above program is similar to the previous program. We declared a recursive function and its base condition. The condition is the lowest value is smaller or equal to the highest value.</p> <ul> <li>We calculate the middle number as in the last program.</li> <li>We have used the <strong>if</strong> statement to proceed with the binary search.</li> <li>If the middle value equal to the number that we are looking for, the middle value is returned.</li> <li>If the middle value is less than the value, we are looking then our recursive function <strong>binary_search()</strong> again and increase the mid value by one and assign to low.</li> <li>If the middle value is greater than the value we are looking then our recursive function <strong>binary_search()</strong> again and decrease the mid value by one and assign it to low.</li> </ul> <p>In the last part, we have written our main program. It is the same as the previous program, but the only difference is that we have passed two parameters in the <strong>binary_search()</strong> function.</p> <p>This is because we can&apos;t assign the initial values to the low, high and mid in the recursive function. Every time the recursive is called the value will be reset for those variables. That will give the wrong result.</p> <h2>Complexity</h2> <p>The complexity of the binary search algorithm is <strong>O(1)</strong> for the best case. This happen if the element that element we are looking find in the first comparison. The <strong>O(logn)</strong> is the worst and the average case complexity of the binary search. This depends upon the number of searches are conducted to find the element that we are looking for.</p> <h2>Conclusion</h2> <p>A binary search algorithm is the most efficient and fast way to search an element in the list. It skips the unnecessary comparison. As the name suggests, the search is divided into two parts. It focuses on the side of list, which is close to the number that we are searching.</p> <p>We have discussed both methods to find the index position of the given number.</p> <hr></=>

Spiegazione:

Nel programma sopra -

• Abbiamo creato una funzione chiamata ricerca_binaria() funzione che accetta due argomenti: una lista da ordinare e un numero da cercare.
• Abbiamo dichiarato due variabili per memorizzare i valori più basso e più alto nell'elenco. Al minimo viene assegnato il valore iniziale su 0, alto A len(lista1) - 1 e metà come 0.
• Successivamente, abbiamo dichiarato il Mentre loop con la condizione che il più basso è uguale e più piccolo di più alto Il ciclo while verrà ripetuto se il numero non è stato ancora trovato.
• Nel ciclo while troviamo il valore medio e confrontiamo il valore dell'indice con il numero che stiamo cercando.
• Se il valore dell'indice medio è inferiore a N , aumentiamo il valore medio di 1 e lo assegniamo a La ricerca si sposta a sinistra.
• Altrimenti, diminuisci il valore medio e assegnalo a alto . La ricerca si sposta sul lato destro.
• Se n è uguale al valore medio, ritorna metà .
• Ciò avverrà fino al Basso è uguale e più piccolo di alto .
• Se arriviamo alla fine della funzione, l'elemento non è presente nell'elenco. Restituiamo -1 alla funzione chiamante.

Comprendiamo il metodo ricorsivo della ricerca binaria.

Ricerca binaria ricorsiva

Il metodo ricorsivo può essere utilizzato nella ricerca binaria. In questo, definiremo una funzione ricorsiva che continua a chiamare se stessa finché non soddisfa la condizione.

Comprendiamo il programma sopra usando la funzione ricorsiva.

Programma Python

 # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print('Element is present at index', str(res)) else: print('Element is not present in list1') 

Produzione:

 Element is present at index 2 

Spiegazione

Il programma sopra è simile al programma precedente. Abbiamo dichiarato una funzione ricorsiva e la sua condizione di base. La condizione è che il valore più basso sia inferiore o uguale al valore più alto.

• Calcoliamo il numero medio come nell'ultimo programma.
• Abbiamo utilizzato il Se istruzione per procedere con la ricerca binaria.
• Se il valore medio è uguale al numero che stiamo cercando, viene restituito il valore medio.
• Se il valore medio è inferiore al valore, stiamo cercando la nostra funzione ricorsiva ricerca_binaria() di nuovo e aumentare il valore medio di uno e assegnarlo a basso.
• Se il valore medio è maggiore del valore che stiamo cercando, allora la nostra funzione ricorsiva ricerca_binaria() di nuovo e diminuire il valore medio di uno e assegnarlo a basso.

Nell'ultima parte abbiamo scritto il nostro programma principale. È lo stesso del programma precedente, ma l'unica differenza è che abbiamo passato due parametri nel file ricerca_binaria() funzione.

Questo perché non possiamo assegnare i valori iniziali a basso, alto e medio nella funzione ricorsiva. Ogni volta che viene chiamato il ricorsivo, il valore verrà reimpostato per quelle variabili. Ciò darà il risultato sbagliato.

Complessità

La complessità dell'algoritmo di ricerca binaria è O(1) per il caso migliore. Ciò accade se l'elemento che stiamo cercando trova nel primo confronto. IL O(log) è il peggiore e la complessità media del caso della ricerca binaria. Dipende dal numero di ricerche condotte per trovare l'elemento che stiamo cercando.

alternativa a xampp

Conclusione

Un algoritmo di ricerca binaria è il modo più efficiente e veloce per cercare un elemento nell'elenco. Salta il confronto non necessario. Come suggerisce il nome, la ricerca è divisa in due parti. Si concentra sul lato dell'elenco, vicino al numero che stiamo cercando.

Abbiamo discusso entrambi i metodi per trovare la posizione dell'indice del numero specificato.