Algoritmos y estructuras de datos en Go: guía práctica

Algoritmos y estructuras de datos en Go: de la teoría a la práctica

Go (Golang) es un lenguaje compilado moderno que combina el rendimiento de C con la simplicidad de Python. Sin embargo, para escribir código eficiente en Go, no basta con conocer la sintaxis. Comprender los algoritmos y las estructuras de datos es la clave para crear aplicaciones rápidas y escalables. En este artículo, analizaremos tres temas fundamentales: búsqueda binaria, tablas hash y ordenamiento, con ejemplos de código reales en Go.

1. Búsqueda binaria: velocidad y precisión

La búsqueda binaria es un algoritmo clásico para buscar un elemento en un array ordenado. En lugar de una búsqueda lineal (O(n)), reduce el espacio de búsqueda a la mitad en cada paso, funcionando en O(log n). En Go, esto es especialmente relevante para trabajar con slices grandes.

Implementación en Go:

package main

import "fmt"

// BinarySearch devuelve el índice del elemento si se encuentra, de lo contrario -1func BinarySearch(arr []int, target int) int {    left, right := 0, len(arr)-1

    for left <= right {        mid := left + (right-left)/2 // protección contra desbordamiento

        if arr[mid] == target {            return mid        } else if arr[mid] < target {            left = mid + 1        } else {            right = mid - 1        }    }    return -1}

func main() {    data := []int{2, 5, 8, 12, 16, 23, 38, 45, 56, 72}    target := 23    index := BinarySearch(data, target)    fmt.Printf("Índice del elemento %d: %d", target, index) // Salida: Índice del elemento 23: 5}

Consejos prácticos:

• Verifique siempre que el array esté ordenado. En Go, puede usar sort.Ints() del paquete sort.
• La fórmula mid := left + (right-left)/2 evita el desbordamiento de enteros en arrays grandes.
• Para trabajar con cadenas, use sort.SearchStrings() de la biblioteca estándar.

2. Tablas hash: acceso rápido a los datos

En Go, la tabla hash incorporada es map. Proporciona acceso a los elementos en O(1) en promedio. Pero es importante entender cómo funciona internamente para evitar "trampas". La tabla hash utiliza una función hash para convertir la clave en un índice de array (bucket). Las colisiones se resuelven mediante el método de encadenamiento (listas separadas para cada bucket).

Ejemplo de trabajo con map:

package main

import "fmt"

func main() {    // Creación de map    scores := make(map[string]int)    scores["Ana"] = 95    scores["Boris"] = 87    scores["Víctor"] = 92

    // Búsqueda con verificación de existencia    name := "Boris"    if score, exists := scores[name]; exists {        fmt.Printf("Calificación de %s: %d", name, score)    } else {        fmt.Printf("Estudiante %s no encontrado", name)    }

    // Eliminación    delete(scores, "Ana")

    // Iteración (¡el orden no está garantizado!)    for key, value := range scores {        fmt.Printf("%s: %d", key, value)    }}

Puntos importantes:

• Map en Go es un tipo de referencia. Al pasarlo a una función, los cambios se reflejarán en el original.
• No use un map nil para escribir; esto causará pánico. Siempre inicialice con make().
• El orden de iteración sobre un map no es determinista. Si necesita un orden, use un slice de claves separado.
• Para las claves, solo se pueden usar tipos comparables: números, cadenas, booleanos, punteros, estructuras sin slices/maps.

3. Ordenamiento: de burbuja a rápido

Go ofrece un potente paquete sort que implementa ordenamiento rápido (quicksort) y otros algoritmos. Pero con fines educativos y de comprensión, es importante escribir el ordenamiento manualmente. Consideremos dos implementaciones: ordenamiento de burbuja (O(n²)) para datos pequeños y ordenamiento rápido (O(n log n)) para grandes