Algoritmo de búsqueda binaria implementado en Go

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 susortpaquete, ensort.Search().

Veamos el uso de la API, extraído de la documentación del paquete, para que sepamos quésort.Searchdeberí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">&gt;=</span> <span style="color:#a6e22e">x</span> })
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">i</span> &lt; len(<span style="color:#a6e22e">a</span>) <span style="color:#f92672">&amp;&amp;</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.Searchdevuelve 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.Searchestá 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 longitudny 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:

ies0,jes9.
hse calcula como(0 + (9-0) / 2)=4
a[h]es15. Esto significa que ejecutamosj = h

Iteración 2:

ies0,jes4.
hse 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] <= xen vez dea[i] >= x.