Duas formas de procurar um elemento na lista — e um truque clássico para otimizar o loop de busca
A busca mais simples possível: percorrer a lista do início ao fim, comparando cada elemento com a chave procurada. Se encontrar, retorna o índice. Se chegar ao final sem encontrar, retorna ERRO.
Comparação direta com Java:
| Operação | C (nossa lista) | Java (ArrayList) |
|---|---|---|
| Busca por valor | buscaSequencial(&lista, 4) → retorna índice ou -1 |
lista.indexOf(4) → retorna índice ou -1 |
| Algoritmo interno | Explícito — você escreve o while | Oculto — ArrayList faz internamente |
| Exige lista ordenada? | Não | Não |
| Complexidade | O(n) | O(n) |
Esta é a implementação direta e natural:
int buscaSequencial(LISTA* l, TIPOCHAVE ch) {
int i = 0;
while (i < l->nroElem) {
if (ch == l->A[i].chave) return i; // achou — retorna o índice
else i++;
}
return ERRO; // não achou — retorna -1
} /* buscaSequencial */
A cada iteração do while, o loop faz duas verificações:
i < l->nroElemch == l->A[i].chavePara uma lista com n elementos onde a chave não existe, são feitas 2n comparações no total. É aqui que entra a otimização com sentinela.
A ideia é elegante: colocamos a própria chave procurada na posição A[nroElem] (a posição "extra" que reservamos com MAX+1). Isso garante que a chave sempre será encontrada em algum ponto — então o while não precisa mais verificar o limite!
int buscaSentinela(LISTA* l, TIPOCHAVE ch) {
int i = 0;
l->A[l->nroElem].chave = ch; // coloca a sentinela na posição extra
while (l->A[i].chave != ch) i++; // uma única verificação por iteração!
if (i > l->nroElem - 1) return ERRO; // parou na sentinela — não achou
else return i; // parou antes — achou de verdade
} /* buscaSentinela */
while para nessa posição (antes de nroElem). Se não existe, o while para na sentinela (posição nroElem). Em ambos os casos, o loop sempre termina — sem precisar verificar i < nroElem.
| Sem sentinela | Com sentinela | |
|---|---|---|
| Verificações por iteração | 2 (limite + chave) | 1 (só chave) |
| Condição do while | i < nroElem && A[i] != ch |
A[i] != ch |
| Exige posição extra no array? | Não — funciona com A[MAX] |
Sim — exige A[MAX+1] |
| Complexidade | O(n) | O(n) |
| Velocidade prática | Base | Ligeiramente mais rápida (metade das comparações) |
| Exige lista ordenada? | Não | Não |
int main() {
LISTA lista;
inicializarLista(&lista);
REGISTRO reg;
reg.chave=9; inserirElemLista(&lista, reg, 0);
reg.chave=3; inserirElemLista(&lista, reg, 1);
reg.chave=4; inserirElemLista(&lista, reg, 2);
reg.chave=1; inserirElemLista(&lista, reg, 3);
reg.chave=12; inserirElemLista(&lista, reg, 2); // insere 12 na posição 2
exibirLista(&lista);
// Lista: " 9 3 12 4 1 "
printf("Busca por 4 (sem sentinela): posição %d\n",
buscaSequencial(&lista, 4));
printf("Busca por 4 (com sentinela): posição %d\n",
buscaSentinela(&lista, 4));
printf("Busca por 99 (inexistente): posição %d\n",
buscaSequencial(&lista, 99));
return 0;
}
Lista: " 9 3 12 4 1 "
Busca por 4 (sem sentinela): posição 3
Busca por 4 (com sentinela): posição 3
Busca por 99 (inexistente): posição -1