Vetor ordenado

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (414 palavras )
  • Download(s) : 0
  • Publicado : 1 de abril de 2013
Ler documento completo
Amostra do texto
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 vetorcrescente  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 deprojeto


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á — bastacomparar 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 == 0entã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 vetortivesse 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. Sex 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 | |Precisamostomar 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 fazsentido 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, intn, 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 é...
tracking img