Ricerca binaria in Go

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

package main

import "fmt"

func main() {
	arr := []int{20, 32, 51, 106, 400}
	x := 51

	result := binarySearch(arr, 0, len(arr)-1, x)

	if result == -1 {
		fmt.Println("Elemento non trovato")
	} else {
		fmt.Printf("Elemento %d trovato in posizione %dn", x, result)
	}
}

func binarySearch(arr []int, sx int, dx int, x int) int {
	if dx >= sx {
		mid := sx + (dx-sx)/2

		if arr[mid] == x {
			return mid
		}

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

		return binarySearch(arr, mid+1, dx, x)
	}

	return -1
}

Enjoy!