Ricerca binaria in Java

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 Java:

public class Main {

    public static void main(String[] args) {
        int[] arr = { 20, 32, 51, 106, 400 };
        int n = arr.length;
        int x = 106;

        int result = binarySearch(arr, 0, n - 1, x);

        if (result == -1)
        {
            System.out.println("Elemento non trovato");
        }
        else
        {
            System.out.println("Elemento trovato; Indice " + result);
        }
    }

    static int binarySearch(int[] arr, int sx, int rx, int x) {
        if (rx >= sx) {
            int mid = sx + (rx - sx) / 2;

            if (arr[mid] == x) {
                return mid;
            }

            if (arr[mid] > x) {
                return binarySearch(arr, sx, mid - 1, x);
            }

            return binarySearch(arr, mid + 1, rx, x);
        }

        return -1;
    }
}

Enjoy!