🎯 Algoritmo de Busca Binária

Em poucas palavras

Algoritmo que localiza um valor numa lista ordenada dividindo o intervalo de busca ao meio a cada passo: compara o alvo com o elemento central e descarta a metade onde ele não pode estar. Executa em tempo O(log n).

---

📝 Notas e Desenvolvimento

Busca binária é um algoritmo de busca que, dada uma lista A de elementos $A_0{A}_1\dots A_{n-1}$ e tamanho $n$, busca o valor T da seguinte forma:

1. Defina $L$ como 0 e $R$ como $n-1$
2. Se $L>R$, encerre a busca sem sucesso
3. Defina $m=\frac{L+R}{2}$ de forma arredondada.
4. Se $T>A_m$, defina $L$ como $m+1$ e retorne ao passo 2
5. Se $T<A_m$, defina $R$ como $m-1$ e retorne ao passo 2.
6. Se $T=A_m$, a busca termina com sucesso

Com base em Análise assintótica, este algoritmo leva $O(\log n)$ tempo

---

📚 Referências e Fontes

🔗 Conexões do Cofre

🌐 Referências Externas

💬 Citações Diretas