logo

TechCodeview

Programma Python per ricerca binaria (ricorsiva e iterativa)

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

  1. Confronta x con l'elemento centrale.
  2. Se x corrisponde all'elemento centrale, restituiamo l'indice medio.
  3. 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.
  4. 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'>)> 

>

atoi c 

>

elenco su Java
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 ')> 

>

>

stringa dell'elenco Java
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

qual è la dimensione dello schermo del mio computer? 
Element is present at index 3>

Complessità temporale : O(log n)

Spazio ausiliario : O(1)