Algoritmos e Estruturas de Dados em Go: Guia Prático

Algoritmos e Estruturas de Dados em Go: da Teoria à Prática

Go (Golang) é uma linguagem compilada moderna que combina o desempenho do C com a simplicidade do Python. No entanto, para escrever código eficiente em Go, não basta conhecer a sintaxe. Compreender algoritmos e estruturas de dados é a chave para criar aplicações rápidas e escaláveis. Neste artigo, abordaremos três tópicos fundamentais: busca binária, tabelas hash e ordenação, com exemplos reais de código em Go.

1. Busca Binária: Velocidade e Precisão

A busca binária é um algoritmo clássico para encontrar um elemento em um array ordenado. Em vez de uma varredura linear (O(n)), ela reduz o espaço de busca pela metade a cada etapa, operando em O(log n). Em Go, isso é especialmente relevante para trabalhar com slices grandes.

Implementação em Go:

package main

import "fmt"

// BinarySearch retorna o índice do elemento se encontrado, caso contrário -1func BinarySearch(arr []int, target int) int {    left, right := 0, len(arr)-1

    for left <= right {        mid := left + (right-left)/2 // proteção contra estouro

        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 do elemento %d: %d", target, index) // Saída: Índice do elemento 23: 5}

Dicas Práticas:

• Sempre verifique se o array está ordenado. Em Go, use sort.Ints() do pacote sort.
• A fórmula mid := left + (right-left)/2 previne estouro de inteiros em arrays grandes.
• Para trabalhar com strings, use sort.SearchStrings() da biblioteca padrão.

2. Tabelas Hash: Acesso Rápido aos Dados

Em Go, a tabela hash embutida é o map. Ela fornece acesso aos elementos em O(1) em média. Mas é importante entender como funciona internamente para evitar "armadilhas". A tabela hash usa uma função hash para transformar a chave em um índice de array (bucket). Colisões são resolvidas pelo método de encadeamento (listas separadas para cada bucket).

Exemplo de trabalho com map:

package main

import "fmt"

func main() {    // Criando um map    scores := make(map[string]int)    scores["Ana"] = 95    scores["Bruno"] = 87    scores["Carlos"] = 92

    // Busca com verificação de existência    name := "Bruno"    if score, exists := scores[name]; exists {        fmt.Printf("Nota de %s: %d", name, score)    } else {        fmt.Printf("Aluno %s não encontrado", name)    }

    // Remoção    delete(scores, "Ana")

    // Iteração (a ordem não é garantida!)    for key, value := range scores {        fmt.Printf("%s: %d", key, value)    }}

Pontos Importantes:

• Map em Go é um tipo de referência. Ao passar para uma função, as alterações refletirão no original.
• Não use um map nil para escrita — isso causará pânico. Sempre inicialize com make().
• A ordem de iteração em um map não é determinística. Se precisar de ordem, use um slice separado de chaves.
• Para chaves, só podem ser usados tipos comparáveis: números, strings, booleanos, ponteiros, structs sem slices/maps.

3. Ordenação: Da Bolha à Rápida

Go oferece um pacote poderoso sort, que implementa a ordenação rápida (quicksort) e outros algoritmos. Mas para fins educacionais e compreensão, é importante escrever a ordenação manualmente. Vamos considerar duas implementações: a ordenação bolha (O(n²)) para dados pequenos e a ordenação rápida (O(n log n)) para dados grandes