驴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.