Busca Binária (Binary Search) em Go
Tags: go, algorithms, computerscience, fundamental
Published: 2023-10-06 21:33:53

_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!