Home Show me the Code Busca binária em Go

Busca binária em Go

0
0
311

Um algoritmo de busca binária é uma estratégia de pesquisa utilizada para encontrar elementos dentro de uma lista, reduzindo consistentemente a quantidade de dados a serem pesquisados, aumentando assim a velocidade com o que o termo da pesquisa é encontrado.
Para usar um algoritmo de pesquisa binária, nossa lista precisa estar ordenada. O algoritmo primeiro encontra a mediana da lista, somando o primeiro e último índice da lista, dividindo o resultado por 2.

Primeiro vamos ordenar nosso slice da seguinte forma:

items := []int{1,2, 9, 20, 31, 45, 63, 70, 100}
sort.Ints(items)

Função que cria a pesquisa binária:

func pesquisaBinaria(needle int, haystack []int) bool {
low := 0
high := len(haystack) - 1
for low <= high{
median := (low + high) / 2
if haystack[median] < needle {
low = median + 1
}else{
high = median - 1
}
}
if low == len(haystack) || haystack[low] != needle {
return false
}
return true
}

A seguir, o programa completo, com a função main:

package main
import "fmt"
func pesquisaBinaria(needle int, haystack []int) bool {
low := 0
high := len(haystack) - 1
for low <= high{
median := (low + high) / 2
if haystack[median] < needle {
low = median + 1
}else{
high = median - 1
}
}
if low == len(haystack) || haystack[low] != needle {
return false
}
return true
}
func main(){
items := []int{1,2, 9, 20, 31, 45, 63, 70, 100}
sort.Ints(items)
fmt.Println(pesquisaBinaria(63, items))
}

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Veja Também

Validação de CPF e CNPJ em Go

Simples e direto. Funções para validar CPF e CNPJ em Go. …