Busca Binária (Binary Search) em Go

O que eu considero que você já conheça para entender o assunto:

• Álgebra básica -> Tendo a função f(x) = x * 2, qual o valor de f(10)? Se você respondeu 20, vamos adiante!

Busca Binária

Vamos começar entendendo o problema que queremos resolver. Se você, assim como eu, começou na escola antes do advento da internet e dispositivos móveis, já deve ter tido a experiência de buscar uma palavra do dicionário de forma manual. Imagine buscar a palavra zebra.
Se não pensarmos em nenhum algoritmo de busca, vamos começar pela letra A, e vamos lendo página por página, todas as palavras até encontrar a palavra zebra. Já pensou em quantas palavras serão lidas até que o resultado seja encontrado? Certamente, você não faria essa busca desta forma pouco inteligente. Você sabe que zebra começa com Z e o dicionário está estruturado e organizado em ordem alfabética. Você irá abrir o dicionário o mais próximo possível do final em busca das palavras que iniciam com a letra Z.
Este é um problema bem comum relacionado à buscas, e um dos algoritmos mais simples para resolver, é a busca binária. Em um algoritmo de busca binária, temos como entrada uma lista ordenada de elementos. Ao executar a busca binária, o retorno do algoritmo deve ser a posição do elemento buscado na lista. Não encontrando, deve haver um retorno definido como um nil.
Vamos pensar um outro exemplo. Um programa bem básico que desenvolvemos ao longo do nosso aprendizado de uma linguagem, é o de adivinhação de um número entre um range de 'x' a 'y'. Toda vez que você 'chutar' um número, o programa retorna uma resposta que pode ser:

• Acertou, no caso de o número chutado ser igual o número à ser adivinhado.
• Alto, caso tenha chutado um número acima do número à ser adivinhado.
• Baixo, caso tenha chutado um número abaixo do número à ser adivinhado.

Pensemos em um range de 1 a 100. Se o número a ser adivinhado for o 80, e buscarmos um a um, teremos realizado 80 consultas até encontrar o resultado. Este algoritmo é chamado de busca simples.
Quando percebemos que a busca simples não é um algoritmo viável para grandes quantidades de dados, precisamos buscar alternativas. Um dos mais simples caminhos para reduzir drasticamente a quantidade de passos para encontrar o dado que estamos buscando é a utilização de uma busca binária.

Vamos escrever um algoritmo em Go implementando uma busca binária.

package main

import (
    "fmt"
    "math/rand"
)

func main() {

    var possiveisNumeros []int
    for i := 1; i <= 100; i++ {
        possiveisNumeros = append(possiveisNumeros, i)
    }

    procurado := rand.Intn(100) + 1

    itemDaLista := binarySearch(possiveisNumeros, procurado)
    fmt.Println("Encontrei o número", itemDaLista)

}

func binarySearch(lista []int, procurado int) int {
    baixo := 0
    alto := len(lista) - 1


    for {
        meio := (baixo + alto) / 2
        if lista[meio] == procurado {
            return lista[meio]
        }
        if lista[meio] > procurado {
            alto = meio - 1
        } else {
            baixo = meio + 1
        }

    }

}

Explicando o que fizemos:
func binarySearch(lista []int, procurado int) int {
declaramos a função onde implementamos a busca binária. Ela recebe 2 parâmetros, um slice de int e o número que estamos procurando.
baixo := 0
alto := len(lista) - 1
passos := 0
baixo e alto acompanham a parte da lista onde estamos buscando a informação.
passos será um contador de quantos passos foram dados até que se encontrasse o valor procurado.
for {
Como não temos while em Go, podemos usar um loop infinito com uma regra de break.
meio := (baixo + alto) / 2
if lista[meio] == procurado {
return lista[meio]
}
Aqui, no if validamos a regra de break. Enquanto não conseguir chegar em um único elemento, nosso for seguirá sendo executado. Enquanto meio busca o elemento central da nossa lista.
if lista[meio] > procurado {
alto = meio - 1
} else {
baixo = meio + 1
}
Aqui verificamos se a tentativa de acerto foi alta ou baixa. Dependendo do resultado, alteramos o valor de alto ou baixo para removermos metade da lista e realizar a próxima iteração do nosso for somente na metade que restou.

Com isto, concluímos uma implementação simples de busca binária. Em breve, volto com uma melhoria desta implementação, utilizando um map de chave e valor, onde buscaremos um valor e retornaremos a chave.

Bons códigos e até a próxima!