Explicando Busca Binária de Forma Simples

Hoje vou tentar explicar a busca binária de forma simples. A busca binária é um algoritmo de busca que encontra a posição de um valor dentro de um array ordenado. O array ser ordenado é um ponto importante aqui.

Para explicar a busca binária, precisamos de um array como exemplo.

arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Neste array, temos 10 elementos, de 1 a 10. A busca binária funciona comparando o valor procurado com o elemento do meio do array.

Por exemplo, se quisermos encontrar o número 5 no array, começamos comparando 5 com o elemento do meio do array, que é 6.

O próximo passo é comparar 5 com 6. Se 5 for menor que 6, podemos descartar a metade direita do array. O novo array fica assim:

arr := []int{1, 2, 3, 4, 5}

Agora repetimos o processo, comparando 5 com o elemento do meio do novo array, que é 3.

O próximo passo é comparar 5 com 3. Se 5 for maior que 3, podemos descartar a metade esquerda do array. O novo array fica assim:

arr := []int{4, 5}

Agora repetimos o processo, comparando 5 com o elemento do meio do novo array, que é 5. E encontramos o número 5 no array.

Neste exemplo simples, encontramos o número 5 em 3 passos. Essa é minha explicação simples da busca binária.

Agora posso implementar o algoritmo de busca binária em Go.

package main

func search(arr []int, searchItem int) int {
	minus := 0
	max := len(arr) - 1

	for minus <= max {
		middle := (minus + max) / 2
		tryFind := arr[middle]
		if tryFind == searchItem {
			return middle
		}
		if tryFind > searchItem {
			max = middle - 1
		} else {
			minus = middle + 1
		}
	}

	return -1
}

Agora posso usar a função search para encontrar o número 5 no array.

func main() {
	arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	searchItem := 80
	pos := search(arr, searchItem)
	var message string
	message = fmt.Sprintf("Find item %d in %d position", searchItem, searchItem)
	if pos == -1 {
		message = fmt.Sprintf("Item %d not found", searchItem)
	}
	fmt.Println(message)
}

Esta é a saída do programa:

Item 80 not found

Este algoritmo me lembra uma frase que ouço com frequência: dividir para conquistar! Espero que este post, junto com os outros, ajude você nos seus estudos e, mais importante, ajude você a entender que o melhor caminho é sempre o do conhecimento profundo!

Até a próxima! Obrigado por ler meu blog. Abraços!