PROGRAMMA PYTHON PER LA RICERCA BINARIA (RICORSIVA E ITERATIVA) - TECHCODEVIEW.COM

In poche parole, questo algoritmo di ricerca sfrutta una raccolta di elementi già ordinati ignorando la metà degli elementi dopo un solo confronto.

Confronta x con l'elemento centrale.
Se x corrisponde all'elemento centrale, restituiamo l'indice medio.
Altrimenti se x è maggiore dell'elemento centrale, allora x può trovarsi solo nel mezzo sottoarray destro (maggiore) dopo l'elemento centrale. Quindi applichiamo nuovamente l'algoritmo per la metà destra.
Altrimenti se x è più piccolo, il bersaglio x deve trovarsi nella metà sinistra (inferiore). Quindi applichiamo l'algoritmo per la metà sinistra.

Programma Python per la ricerca binaria utilizzando la ricorsiva

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>> => low:> > mid> => (high> +> low)> /> /> 2> > # If element is present at the middle itself> > if> arr[mid]> => => x:> > return> mid> > # If element is smaller than mid, then it can only> > # be present in left subarray> > elif> arr[mid]>x:> > return> binary_search(arr, low, mid> -> 1> , x)> > # Else the element can only be present in right subarray> > else> :> > return> binary_search(arr, mid> +> 1> , high, x)> > else> :> > # Element is not present in the array> > return> -> 1> # Test array> arr> => [> 2> ,> 3> ,> 4> ,> 10> ,> 40> ]> x> => 10> # Function call> result> => binary_search(arr,> 0> ,> len> (arr)> -> 1> , x)> if> result !> => -> 1> :> > print> (> 'Element is present at index'> ,> str> (result))> else> :> > print> (> 'Element is not present in array'> )>

Produzione

Element is present at index 3

Complessità temporale : O(log n)

Spazio ausiliario : O(logn) [NOTA: la ricorsione crea stack di chiamate]

Programma Python per la ricerca binaria utilizzando iterativo

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: alto = medio - 1 # significa che x è presente a metà else: return mid # Se raggiungiamo qui, l'elemento non era presente return -1 # Test array arr = [ 2, 3, 4, 10, 40 ] x = 10 # Risultato della chiamata di funzione = ricerca_binaria(arr, x) if risultato != -1: print('L'elemento è presente nell'indice', str(risultato)) else: print('L'elemento non è presente nell'array ')>

Produzione

Element is present at index 3

Complessità temporale : O(log n)

Spazio ausiliario : O(1)

Programma Python per la ricerca binaria utilizzando il modulo bisect integrato

Approccio passo dopo passo:

Il codice importa il modulo bisect che fornisce il supporto per la ricerca binaria.
Viene definita la funzione Binary_search_bisect() che accetta un array arr e l'elemento per cercare x come input.
La funzione chiama la funzione bisect_left() del modulo bisect che trova la posizione dell'elemento nell'array ordinato arr dove x dovrebbe essere inserito per mantenere l'ordine ordinato. Se l'elemento è già presente nell'array, questa funzione restituirà la sua posizione.
La funzione controlla quindi se l'indice restituito i rientra nell'intervallo dell'array e se l'elemento in quell'indice è uguale a x.
Se la condizione è vera, la funzione restituisce l'indice i come posizione dell'elemento nell'array.
Se la condizione è falsa, la funzione restituisce -1 indicando che l'elemento non è presente nell'array.
Il codice definisce quindi un array arr e un elemento x da cercare.
La funzione binaria_search_bisect() viene chiamata con arr e x come input e il risultato restituito viene memorizzato nella variabile risultato.
Il codice controlla quindi se il risultato non è uguale a -1, indicando che l'elemento è presente nell'array. Se vero, stampa la posizione dell'elemento nell'array.
Se il risultato è uguale a -1, il codice stampa un messaggio indicante che l'elemento non è presente nell'array.

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'> )>

Produzione