pesquisa binária

Projeto de Algoritmos
Home

|

Prefácio

|

Livros

|

Sítios WWW

|

Índice

"Binary search is to algorithms what a wheel is to mechanics:
It is simple, elegant, and immensely important."
—Udi Manber, Introduction to Algorithms
"A good algorithm is like a sharp knife: it does what it is supposed to do with a minimum amount of applied effort.
Using the wrong algorithm to solve a problem is like trying to cut a steak with a screwdriver: you may eventually get a digestible result, but you will expend considerably more effort than necessary, and the result is unlikely to be aesthetically pleasing."
—Th. Cormen, Ch. Leiserson, R. Rivest, Introduction to Algorithms
"Binary search is a notoriously tricky algorithm to program correctly.
It took seventeen years after its invention until the first correct version of binary search was published!"
—Steven Skiena, The Algorithm Design Manual

Busca em vetor ordenado
Esta página estuda o seguinte problema básico: determinar se um dado número está ou não está em um dado vetor ordenado. Mais precisamente, dado um número x e um vetor crescente v[0..n-1], encontrar um índice j tal que v[j] == x .
Vamos examinar dois algoritmos para o problema: um óbvio e lento e outro sofisticado e muito mais rápido.
Veja o verbete Binary search algorithm na Wikipedia.

Decisões de projeto
Comecemos por tornar o problema um pouco mais elaborado: vamos exigir que o algoritmo devolva j tal que v[j-1] < x ≤ v[j] .

Assim, o usuário ficará sabendo onde x está — basta comparar x com v[j] — ou onde deveria estar. Para que a coisa fique completa, devemos permitir que j valha 0 ou n. Nesses casos a condição acima deve ser interpretada com inteligência: se j == 0 então a condição se reduz a x ≤ v[0] ,

pois v[-1] não faz sentido; se j == n então a condição se reduz a v[n-1] < x,

pois v[n] não faz sentido. Tudo se passa como se nosso vetor tivesse um componente imaginário v[-1] com valor infinito