Ricerca binaria in Python
La ricerca binaria è un algoritmo che viene usato per trovare gli elementi in un array ordinato; il fatto che sia ordinato è fondamentale e obbligatorio.
Questo algoritmo è più efficiente della ricerca sequenziale, in quanto usa la logica del divide et impera.
In sostanza si procede suddividendo l'array man mano che la ricerca non trova l'elemento, andando a ricercarlo solo in una parte dell'array, che diventa sempre più piccolo.
Quindi, partendo da un elemento casuale:
- se la chiave è uguale, abbiamo trovato l'elemento
- se la chiave è maggiore si prosegue cercando verso destra
- se la chiave è minore si prosegue cercando verso sinistra
Ecco perchè l'array deve essere ordinato.
