Algoritmo di Ricerca Binaria in Python.

Conoscendo python e le potenzialità di cui è dotato questo linguaggio, il codice sottostante vi apparirà abbastanza rudimentale. E’ un algoritmo di Ricerca Binaria. Python integra nelle sue librerie base, svariati algoritmi di ricerca o ordinamento che hanno una complessità computazionale ottima. Per la ricerca vengono usate tabelle hash (dunque in fase di assegnazione, tramite apposite funzioni iniettive, si inseriscono gli elementi nelle varie posizioni e si consuma un pò più di memoria per compensare successivamente in termini di tempo la ricerca). Quindi detto questo, l’algoritmo d’esempio sotto è fine a se stesso, con una complessità computazionale logaritmica (log_2n) non uguaglia certamente le prestazioni di una ricerca hash. Ma è comunque perfetto per esercitarsi e prendere spunto per scrivere qualcosa di analogo, in altri linguaggi, che sono sprovvisti di librerie con algoritmi di ricerca efficenti.

#Ricerca in lista ordinata, tramite Algoritmo di Ricerca Binaria: O(log_2n).
 
#Funzione di ricerca.
 
def Ricerca_binaria(lista, n, x):
  '''Funzione di ricerca binaria.'''
  i = 0
  j = n-1  
  while(i <= j):
    medio = (i+j)/2
    if (x < lista[medio]):
      j = medio - 1
    elif (x > lista[medio]):
      i = medio + 1
    else:
      return medio
  return -1
 
#MAIN.
 
l = [3, 4, 5, 13, 20, 21, 30, 33, 34, 35] #Lista di esempio.
 
i = Ricerca_binaria(l, 10, input("Inserisci un numero da ricercare nella lista: "))
 
if (i >= 0):
  print "\nElemento trovato nella posizione %s\n" % i 
else:
  print "Elemento non trovato!", -1

Algorithm’s type: Divide et impera.