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.

Qui sotto un esempio in Python:

def binary_search(arr, low, high, x):
    if high >= low:

        mid = (high + low) // 2

        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)
        else:
            return binary_search(arr, mid + 1, high, x)
    else:
        return -1

if __name__ == '__main__':
    arr = [20, 32, 51, 106, 400]
    x = 106
    result = binary_search(arr, 0, len(arr) - 1, x)
    print(result)

Enjoy!