A sentinela é utilizada na busca sequencial para eliminar o “if” de dentro do laço, ou seja, na busca sequencial normal a cada iteração do laço o método testa se a chave buscada é a que está passando no laço, e isto pode ser bastante trabalhoso computacionalmente caso o vetor tenha tamanho muito grande.
Já na busca sequencial com sentinela isto não é necessário, basta adicionar o valor buscado ao final do vetor, isto garante que o valor sempre será encontrado, e então percorrer o laço com a condição de parada quando o valor que está passando no laço for igual ao valor pesquisado. Ao final basta testar se o índice do laço é igual ao final do vetor, ou seja, não encontrou o valor, ou se é diferente, neste caso, significa que encontrou o valor buscado.
Para ficar mais claro veja o código em python abaixo:
def BuscaSentinela(vetor, chave): vetor.append(chave) # Coloca a chave na ultima posicao do vetor indice = 0 # Comeca testando da posicao 0 do vetor while vetor[indice] != chave: # Enquanto nao for a chave encontrada continua o laco indice += 1 vetor.pop() # Retira o valor sentinela da ultima posicao if indice == len(vetor)-1: # Se o indice esta igual o tamanho do vetor menos 1 significa que nao encontrou return -1 # Retorna -1 return indice # Caso contrario, encontrou, retorna a posicao da chave no vetor vetor = [1, 4, 5, 2, 42, 34, 54, 98, 89, 78, 67] print BuscaSentinela(vetor, 34) |
Qualquer dúvida ou sugestão é só comentar.
Updated Code 