Algoritmos

Busca Seqüencial com Sentinela

▪ Coloca-se a chave a ser procurada após a último elemento do vetor. ▪ A busca é feita com uma única pergunta, se o elemento na posição i é diferente do procurado (otimizando a condição do for na busca seqüencial tradicional). ▪ Ao terminar deve-se verificar a posição de i, se for igual à posição onde a chave foi inserida “artificialmente” significa que a chave não constava no vetor.
Obs: neste caso o vetor deve ser declarado com tamanho máximo mais 1.

Ex: void main(void)
{
float vet[MAX+1], chave; int tam_log, i; … /*Leitura*/ … scanf(“%f”,&chave); vet[tam_log]=chave; for (i=0;vet[i]!=chave;i++); if (i==tam_log) printf(“Nao achou”); else printf(“Achada a chave na posicao: %d”,i);
}

(outros detalhes na apostila)

Busca Seqüencial em Vetor Ordenado

Nos casos de vetores ordenados, uma otimização extra pode ser feita. Supondo que os elementos estejam ordenados crescentemente, ao se buscar uma chave dentro do vetor, ela nunca poderá estar após um elemento maior que o seu valor. Ou seja, a busca seqüencial pode parar quando o valor do elemento atual é maior que o da chave.

Exemplo:
Chave:
|34 |

Vetor:
|8 |12 |16 |29 |38 |41 |47 |53 |68 |97 |
|0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |

Quando o índice da busca chegar a 4 não é mais necessário percorrer o resto do vetor e já é possível afirmar que não existe nenhum elemento com aquela chave.
Exemplo em C: int busca(int vet[],int tam, int chave, int *pos)
{
*pos=0; while(*poschave) return 0; else (*pos)++; return 0;
}

Busca Binária

▪ Só é possível fazer a busca binária se o vetor estiver ordenado. ▪ Método bastante eficiente para fazer busca, reduzindo bastante a complexidade computacional do problema. A quantidade de comparações que devem ser feitas fica na ordem de log n, enquanto nas