Busca binária em Go

Introdução

Algoritmos de busca são extremamente úteis na implementação do mais diversos tipos software, seja você um iniciante ou desenvolvedor mais experiente.

Busca simples

Se você fez faculdade de programação ou algum outro curso que mencione um pouco mais de fundamentos já deve ter se deparado com alguns tipos de algoritmos de busca. O mais simples deles seria o algoritmo de busca simples, o qual consiste em percorrer o array desde o início verificando se cada um dos itens é o que estamos procurando, algo como:

No caso apresentado na imagem acima não parece ser um grande problema. Agora, imagine que em vez de 10 elementos nosso array tem 100.000. Caso o número procurado estiver na última posição do array nosso pior caso terá percorrido todas as posições para encontrá-lo. Não é muito performático.

Busca binária

Uma alternativa bastante interessante e bem mais eficiente é a busca binária:

Dado que nosso array está ordenado, essa característica é essencial, a nossa busca começa a partir do elemento central do array, ou do elemento imediatamente anterior se a lista tiver um número par de elementos.

Caso o elemento em questão seja diferente do procurado nossa busca continua pelo conjunto a esquerda deste. Se o item atual for maior que o procurado a busca continua pelo conjunto a direita.

Esse processo se repete até encontrarmos o elemento procurado ou até sobrar um único item na lista e este não seja nosso alvo, o que quer dizer que ele não está no array.

Comparação

Já nesses dois exemplos extremamente simples podemos notar uma grande diferença pensando no pior caso.

Tomemos agora como exemplo uma busca em um lista com 100 elementos. Ao usar a busca simples poderíamos precisar de até 100 iterações para encontrar o elemento procurado no pior caso. Já usando busca binária encontraríamos o elemento, no pior caso, em no máximo 7 etapas.

Na notação de complexidade Big O a busca simples tem uma complexidade de tempo de execução de O(n), já a busca binário é O(log n), significativamente mais eficiente.

Implementação em Go

Vemos abaixo a implementação a busca binário em Go, que é uma linguagem extremamente eficiente e um dos motivos por isso é por ela ser compilada.

package main

import "fmt"

func main() {
	// Lista em que faremos a busca
	list := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	fmt.Println("List:", list)

	// número que será procurado
	number := 10
	fmt.Println("Número procurado:", number)

	// exibe o posição na lista em que o número está ou -1 caso não seja encontrado
	fmt.Println("Posição:", binarySearch(list, number))
}

func binarySearch(list []int, number int) int {
  // índice mais baixo do conjunto atual em que a busca está sendo feita
	low := 0
  // índice mais alto do conjunto atual em que a busca está sendo feita
	high := len(list) - 1

  // iteramos a lista até que ela tenha somente um elemento
	for low <= high {
    // pegamos o elemento do meio da lista
    // Go arredonda pra baixo caso tentemos guardar numa variável
    // do tipo int um valor que não seja inteiro
		middle := (low + high) / 2

    // pegamos o elementro central do intervalo atual
		guess := list[middle]

		if guess == number {
      // se encontramos o númeor procurado, retornamos o índice do elemento
			return middle
		} else if guess > number {
      // se nosso chute é maior que o elemento buscado
      // configuramos o maior índice do intervalo de busca como o item imediatamente
      // anterior ao atual
			high = middle - 1
		} else {
      // se chute é menor que o elemento buscado
      // configuramos o menor índice do intervalo de busca como o item imediatamente
      // posterior ao atual
			low = middle + 1
		}
	}

  // se depois de percorrer toda a lista e não encontrarmos o elemento, -1 é retornado
  // o que significa que o elemento não está na lista
	return -1
}

Fontes: Livro Entendendo Algoritmos de Aditya Y. Bhargava