🥇 Arreglos, Búsqueda Binaria (Binary Search)

Cuando los datos se encuentran ordenados existen algoritmos mas eficientes que la búsqueda linea, un ejemplo de algoritmo a utilizar en este caso es binary search (busqueda binaria).

🍿 ¿Cómo implementar binary search (búsqueda binaria) en Go?

La búsqueda binaria utiliza define límites de búsqueda en un arreglo. A cada iteración divide la lista en 2 y va realizando comparaciones hasta que el punto medio coincida con el valor a buscar.

func BusquedaBinaria(numeros []int, valor int) int {

	// variables de inicio y fin que limitan los margenes
	// de busqueda
	inicio := 0
	fin := len(numeros)

	// recorrer los elementos mientras inicio sea menor que
	// fin (cuando la lista no este vacia)
	for inicio < fin {

		// obtener el punto medio entre los límites
		puntoMedio := int(math.Floor(float64(inicio+fin) / 2))

		// verificar si...
		switch {

		// el punto medio es igual al valor de busqueda
		// y si es asi retornar dicho valor
		case numeros[puntoMedio] == valor:
			return puntoMedio

		// si el punto medio es menor que el valor buscado
		// ajustar el limite inicial enseguida del punto medio
		case numeros[puntoMedio] < valor:
			inicio = puntoMedio + 1

		// si es mayor entonces ajustar el limite final
		// a donde se encuentra el punto medio
		default:
			fin = puntoMedio
		}
	}

	// si no se encontro el valor en la lista retornar -1
	return -1
}
func main() {

	numerosEnOrden := []int{}

	for i := 0; i < 1000; i++ {
		numerosEnOrden = append(numerosEnOrden, i)
	}

	fmt.Println("Buscar 5000:", BusquedaBinaria(numerosEnOrden, 5000))
	fmt.Println("Buscar 100:", BusquedaBinaria(numerosEnOrden, 100))

}

Salida.

Buscar 5000:    -1
Buscar 100:     100

Siempre tomar en cuenta que para utilizar la búsqueda binaria es importante que los datos estén ordenados. Si no es así hay que realizar un ordenamiento previo a la búsqueda.