¿Cómo implementar una búsqueda binaria de forma recursiva en Go?
Ya hemos visto la aplicación de la búsqueda binaria utilizando un loop for, esto también lo podemos replicar mediante una función recursiva.
Para implementar una busqueda binaria mediante una función recursiva utilizamos el siguiente algoritmo en Go.
package main
import (
"fmt"
"math"
)
func BusquedaBinaria(lista []int, item int, pos int) int {
if len(lista) <= 0 {
return -1
}
puntoMedio := int(math.Floor(float64(len(lista)) / 2))
switch {
case lista[puntoMedio] == item:
return pos + puntoMedio
case lista[puntoMedio] < item:
return BusquedaBinaria(lista[puntoMedio+1:], item, pos+puntoMedio+1)
default:
return BusquedaBinaria(lista[:puntoMedio], item, pos)
}
}
func main() {
nums := []int{100, 200, 300, 400, 500, 600, 700, 800, 900, 1000}
fmt.Println(100, BusquedaBinaria(nums, 100, 0))
fmt.Println(200, BusquedaBinaria(nums, 200, 0))
fmt.Println(300, BusquedaBinaria(nums, 300, 0))
fmt.Println(400, BusquedaBinaria(nums, 400, 0))
fmt.Println(500, BusquedaBinaria(nums, 500, 0))
fmt.Println(600, BusquedaBinaria(nums, 600, 0))
fmt.Println(700, BusquedaBinaria(nums, 700, 0))
fmt.Println(800, BusquedaBinaria(nums, 800, 0))
fmt.Println(900, BusquedaBinaria(nums, 900, 0))
fmt.Println(1000, BusquedaBinaria(nums, 1000, 0))
}
Salida.
100 0
200 1
300 2
400 3
500 4
600 5
700 -1
800 6
900 7
1000 8
El enfoque de la solución de la búsqueda binaria con una función recursiva es el mismo, utilizar la estrategia de dividir y vencer. Dividimos el slice en 2 y continuamos el mismo proceso una y otra vez hasta encontrar el valor requerido.
