Ricerca binaria in Kotlin

Mattepuffo's logo
Ricerca binaria in Kotlin

Ricerca binaria in Kotlin

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

fun main(args: Array<String>) {
    val arr = intArrayOf(20, 32, 51, 106, 400);
    val n = arr.size;
    val x = 10;

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

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

fun binarySearch(arr: IntArray, sx: Int, rx: Int, x: Int): Int {
    if (rx >= sx) {
        val 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!


Share this Post

Commentami!