logo

Um pouco sobre Binary Search - Algorítimos.

Nov 17 • 3min

O algoritmo de busca binária (Binary search em inglês) ou pesquisa binária, é um algoritmo eficiente para encontrar um determinado valor em um conjunto ordenado de elementos. É comumente usado em programação para buscar elementos em matrizes e listas.

O princípio básico da busca binária é dividir repetidamente o conjunto de elementos pela metade e descartar a metade que não contém o valor que estamos procurando. Isso é feito até que o valor desejado seja encontrado ou até que o conjunto de elementos se torne vazio.

O algoritmo de busca binária funciona em uma matriz ordenada - detalhe importante, em que os elementos são organizados em ordem crescente ou decrescente. Para implementar a busca binária, primeiro determinamos o valor do elemento central da matriz. Se este valor for igual ao valor que estamos procurando, a busca é concluída. Caso contrário, se o valor que estamos procurando for menor que o valor central, procuramos na metade esquerda da matriz. Se o valor que estamos procurando for maior que o valor central, procuramos na metade direita da matriz - Entrando no conceito de dividir para conquistar.

A seguir, vamos ver um exemplo de como o algoritmo de busca binária funciona na prática:

Suponha que temos a matriz ordenada [2, 4, 6, 8, 10, 12, 14, 16] e queremos procurar o valor 10.

Começamos determinando o elemento central da matriz, que é 8. Como 10 é maior que 8, procuramos na metade direita da matriz. Agora, estamos procurando na matriz [10, 12, 14, 16].

Determinamos novamente o elemento central da matriz, que é 14. Como 10 é menor que 14, procuramos na metade esquerda da matriz. Agora, estamos procurando na matriz [10, 12].

Determinamos o elemento central da matriz novamente, que é 12. Como 10 é menor que 12, procuramos na metade esquerda da matriz. Agora, estamos procurando na matriz [10].

Determinamos o elemento central da matriz novamente, que é 10. Como 10 é igual ao valor que estamos procurando, a busca é concluída.

O algoritmo de busca binária tem uma complexidade de tempo de O(log n) - na Notação Big O, onde n é o número de elementos na matriz. Isso torna a busca binária muito mais rápida do que a busca linear, que tem uma complexidade de tempo de O(n) - tenho recomendações sobre Notação Big O. No entanto, a busca binária requer que a matriz esteja ordenada antes de poder ser aplicada.

Em resumo, o algoritmo de busca binária é uma técnica eficiente e útil para buscar elementos em matrizes e listas ordenadas. Ele pode ajudar a melhorar a eficiência e o desempenho de programas que precisam procurar elementos em grandes conjuntos de dados.

comente no

twitter