Busca binária
📚 Introdução
A busca binária é um algoritmo de busca que utiliza a técnica de divisão e conquista, ela é utilizada para buscar um elemento em um vetor ordenado.
A busca binária é um algoritmo de complexidade O(log n), ou seja, ele é muito mais rápido que uma busca linear, que tem complexidade O(n).
Digamos que você tenha um vetor de números inteiros ordenados, e queira buscar o número 7.
O algoritmo da busca binária funciona da seguinte forma:
Verifica o elemento do meio do vetor
Se o elemento do meio for o que você está procurando, retorna o índice dele
Se o elemento do meio for maior que o que você está procurando, repete o processo na primeira metade do vetor
Caso o elemento do meio for menor que o que você está procurando, repete o processo na segunda metade do vetor
Vamos ver um exemplo:
🤓 Implementação
🤔 Observações
É importante notar que a busca binária só funciona pois o vetor está ordenado. Caso o vetor não esteja ordenado, o algoritmo não funciona.
Last updated