Vetor ordenado

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.

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 negativo e um componente imaginário v[n] com valor infinito positivo.

No exemplo abaixo, se x vale 555 então o valor correto de j é 4. Se x vale 1000 então o valor correto de j é 13.

0 | | | | | | | | | | | |n-1 | |111 |222 |333 |444 |555 |555 |666 |777 |888 |888 |888 |999 |999 | |Precisamos tomar mais uma decisão de projeto: qual o menor vetor com que vamos nos preocupar? Suporemos sempre que

n ≥ 1,

pois isso torna o raciocínio mais simples. É verdade, entretanto, que o problema faz sentido mesmo quando n vale 0 (a solução do problema é necessariamente 0 nesse caso).

Busca sequencial

Comecemos com um algoritmo simples e óbvio:

int

busca( int x, int n, int v[]) {

int j = 0;

while (j < n && v[j] < x) ++j;

return j;

}

Quantas comparações de x com elementos de v essa função faz? A resposta é

n