Buscar Binaria

1 minute read

Começamos a praticar algoritmos na mentoria #desenvolvendoMe, mentorada pelo Marco Castro

o assunto dessa semana é sobre pratica de algoritmos, resolvir escrever um post para falar mais sobre os a buscar binaria.

Imagem

Lendo um livro de algoritmo, veio a ideia de escrever sobre o assunto, creio que isso vai melhorar meus conhecimentos sobre algoritmo, irei resumir cada capítulo apenas aquilo que irei julgar importante, o primeiro capítulo vou falar de busca binária que achei muito interessante o formato de buscar.

O algoritmo de busca binária é como se você fosse fazer uma busca em uma lista ordenada e que você precisa encontrar um item, esse algoritmo é eficiente devido a forma que ele divide sistematicamente a pesquisa como na imagem acima.

Normalmente usamos essa busca para encontrar um item dentro do array.

Vamos pensar em uma lista de contatos, vamos procurar um nome e esse nome começa com a letra H, então vou logo pra letra H da agenda certo?

Pois é, busca binária é quase isso, porque quase isso?

Porque, o algoritmo divide os blocos em partes iguais e seleciona um número de cada bloco.

Imagem

Então irei explicar como o algoritmo funciona, mais antes vou dar um exemplo errado de como você não deve criar uma pesquisa,

Se eu pedisse pra adivinhar o número de 1 a 10 você começaria com 1 depois 2, 3, 4, 5, 6, 7, 8, 9, 10. E o número fosse o 10 você ia falar todos os número da lista, isso é uma pesquisa simples que não recomendo fazer lá, porque vai tomar muito tempo.

Agora como iremos fazer com a pesquisa binária, como na imagem acima o algoritmo vai dividir os números em blocos e ele vai escolher 1 número de cada bloco e comparar com o valor pesquisado.

Vamos testar usando ruby como linguagem.

Exemplo:


def binary_search(value, list, first, last)
    mid = ((first + last)/ 2).floor

    if first <= last 
        if value > list[mid]
            first = mid + 1
            binary_search(value, list, first, last)
        elsif value < list[mid]
            last = mid -1
            binary_search(value, list, first, last)
        else 
            mid
        end 
    else
        -1
    end 
end
list = [12, 15, 19, 22, 25, 65, 98, 102, 325]

result = binary_search(19, list, 0, list.size)
puts result