Cómo implementar el algoritmo de búsqueda binaria en Go
Búsqueda binariaes un algoritmo simple para encontrar un elemento en unmatriz ordenada, y generalmente se hace referencia a él como una muestra de código para estudiar al aprender un nuevo lenguaje de programación.
Eficiencia
Es muy eficiente:
- Hora:O (log n), es en el peor de los casos logarítmico
- Espacio:0(1), toma un tiempo constante
Teoría
Dada una matriz ordenada, elegimos el elemento Y en el medio y lo comparamos con el valor objetivo X.
Si Y coincide con X, devolvemos la posición Y y salimos.
Determinamos si X <Y, en este caso descartamos el lado derecho, y vamos por el medio del lado izquierdo, y repetimos la misma operación de arriba.
La búsqueda termina cuando Y finalmente coincide con X. Si esto no sucede, devolvemos la posición que X habría tomado si estuviera en el arreglo.
Implementación
Tenemos suerte, la biblioteca estándar de Go proporciona una implementación de árbol binario en susort
paquete, ensort.Search()
.
Veamos el uso de la API, extraído de la documentación del paquete, para que sepamos quésort.Search
debería regresar:
package main
import (
“fmt”
“sort”
)
func main() {
a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
x := 6
<span style="color:#a6e22e">i</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">sort</span>.<span style="color:#a6e22e">Search</span>(len(<span style="color:#a6e22e">a</span>), <span style="color:#66d9ef">func</span>(<span style="color:#a6e22e">i</span> <span style="color:#66d9ef">int</span>) <span style="color:#66d9ef">bool</span> { <span style="color:#66d9ef">return</span> <span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">i</span>] <span style="color:#f92672">>=</span> <span style="color:#a6e22e">x</span> })
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">i</span> < len(<span style="color:#a6e22e">a</span>) <span style="color:#f92672">&&</span> <span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">i</span>] <span style="color:#f92672">==</span> <span style="color:#a6e22e">x</span> {
<span style="color:#a6e22e">fmt</span>.<span style="color:#a6e22e">Printf</span>(<span style="color:#e6db74">"found %d at index %d in %v\n"</span>, <span style="color:#a6e22e">x</span>, <span style="color:#a6e22e">i</span>, <span style="color:#a6e22e">a</span>)
} <span style="color:#66d9ef">else</span> {
<span style="color:#a6e22e">fmt</span>.<span style="color:#a6e22e">Printf</span>(<span style="color:#e6db74">"%d not found in %v\n"</span>, <span style="color:#a6e22e">x</span>, <span style="color:#a6e22e">a</span>)
}
}
sort.Search
devuelve un índicei
, y solo debemos asegurarnos de que ese índice realmente contengax
.
Por supuesto, queremos saber cómo se implementa esto internamente. Dado que la biblioteca estándar está escrita en Go y es de código abierto, es muy fácil ver cómosort.Search
está implementado:
func Search(n int, f func(int) bool) int {
// Define f(-1) == false and f(n) == true.
// Invariant: f(i-1) == false, f(j) == true.
i, j := 0, n
for i < j {
h := i + (j-i)/2 // avoid overflow when computing h
// i ≤ h < j
if !f(h) {
i = h + 1 // preserves f(i-1) == false
} else {
j = h // preserves f(j) == true
}
}
// i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.
return i
}
Vamos a desglosarlo:
Dada una matriz con longitudn
y una función de comparaciónf
(que evalúa internamentex >= a[h]
), comenzamos a iterar la matriza
.
Usemos los valores reales que usamos en el ejemplo, es más fácil mostrar lo que está sucediendo.
Datos:
a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
x := 6
Iteración 1:
i
es0
,j
es9
.h
se calcula como(0 + (9-0) / 2)
=4
a[h]
es15
. Esto significa que ejecutamosj = h
Iteración 2:
i
es0
,j
es4
.h
se calcula como(0 + (4-0) / 2)
=2
a[h]
es6
. Encontramos la posición dex
, esto significa que volvemosh = 2
Buscando orden inverso
Dado que podemos pasar una función asort.Search
, es fácil buscar en una matriz ordenada en orden inverso, como
a := []int{55, 45, 36, 28, 21, 15, 10, 6, 3, 1}
x := 6
pasando una función que comparaa[i] <= x
en vez dea[i] >= x
.
i := sort.Search(len(a), func(i int) bool { return a[i] <= x })
Más tutoriales de go:
- Uso de NGINX Reverse Proxy para brindar servicios de Go
- Hacer una copia de una estructura en Go
- Los conceptos básicos de un servidor web Go
- Ordenar un tipo de mapa en Go
- Ir consejos en pocas palabras
- Explicación de las etiquetas Go
- Ir al formato de fecha y hora
- Procesamiento JSON con Go
- Ir a funciones variadas
- Hoja de referencia de Go Strings
- Explicación de la interfaz Go Empty
- Depuración de Go con VS Code y Delve
- Parámetros de devoluciones de Go Named
- Generación de cadenas y números aleatorios en Go
- Estructura del sistema de archivos de un proyecto de Go
- Algoritmo de búsqueda binaria implementado en Go
- Uso de indicadores de línea de comando en Go
- GOPATH explicado
- Cree una aplicación de línea de comandos con Go: lolcat
- Construyendo un comando CLI con Go: cowsay
- Uso de Shell Pipes con Go
- Tutorial de Go CLI: clon de la fortuna
- Enumere los archivos en una carpeta con Go
- Use Ir para obtener una lista de repositorios de GitHub
- Ve, agrega un trozo de cadenas a un archivo
- Ve, convierte una cadena en un segmento de bytes
- Visualice sus contribuciones locales de Git con Go
- Introducción a la creación de perfiles de memoria y CPU de Go
- Resolver el error "no admite la indexación" en un programa Go
- Medir el tiempo de ejecución en un programa Go
- Creación de un rastreador web con Go para detectar títulos duplicados
- Siga las mejores prácticas: ¿puntero o receptores de valor?
- Siga las mejores prácticas: ¿Debería utilizar un método o una función?
- Ir a estructuras de datos: Establecer
- Hoja de referencia de Go Maps
- Genere implementaciones para tipos genéricos en Go
- Ir a estructuras de datos: diccionario
- Ir a estructuras de datos: tabla hash
- Implementar oyentes de eventos en canales de paso
- Ir a estructuras de datos: apilar
- Ir a estructuras de datos: cola
- Ir a estructuras de datos: árbol de búsqueda binaria
- Ir a estructuras de datos: gráfico
- Ir a estructuras de datos: lista vinculada
- La guía completa de Go Data Structures
- Comparación de valores de Go
- ¿Go está orientado a objetos?
- Trabajar con una base de datos SQL en Go
- Usar variables de entorno en Go
- Ir al tutorial: API REST respaldada por PostgreSQL
- Habilitación de CORS en un servidor web Go
- Implementación de una aplicación Go en un contenedor Docker
- Por qué Go es un lenguaje poderoso para aprender como desarrollador PHP
- Ve, elimina el carácter de nueva línea io.Reader.ReadString
- Ir, cómo ver los cambios y reconstruir su programa
- Ve, cuenta los meses desde una fecha
- Acceder a los parámetros HTTP POST en Go