🔥 Funciones Recursivas, Búsqueda Binaria (Binary Search)

☆ ¿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.