Home Show me the Code Busca binária em Go

Busca binária em Go

0
0
794

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

Um guia de boas práticas de segurança para desenvolvimento em Go

Confira este livro on-line gratuito sobre boas práticas de segurança de desenvolvimento pa…