LinearSearchSentinel.c

/*
*	Exemplo de Busca Sentinela em C
*	Objetivo: Encontrar um valor em um vetor sem precisar testar todos os valores dentro do laço
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TAM_VETOR 10

// Busca sentinela, realiza uma busca sequencial sem precisar testar a chave a cada passo do laço de busca
int buscaSentinela(int vetor[], int chave){
	vetor[TAM_VETOR] = chave; // Coloca o valor buscado (chave) na última posição do vetor
	int aux = 0; // Variável de controle do laço
	while( vetor[aux] != chave ) // Enquanto não encontrar o valor (chave) incrementa 1 em aux
		aux++;
	if( aux == TAM_VETOR ) // Caso o valor de aux seja igual ao tamanho do vetor, significa que foi até o final e não encontrou o valor
		return -1; // Não encontrou
	else // Caso aux seja diferente, significa que encontrou o valor e quebrou o laço, o aux é a posição do valor buscado
		return aux; // Encontrou
}

int main(){

	int vetor[TAM_VETOR+1]; // Declara o vetor com +1 pois é a posição que será utilizada pela sentinela

	// Preenche o vetor com valores aleatórios 0-1000
	srand(time(NULL));
	for(int i = 0; i < TAM_VETOR; i++){
		vetor[i] = rand()%1000;
		printf("%d, ", vetor[i]);
	}

	// Faz a busca, passando como parâmetro o vetor e a chave que deseja buscar
	int res = buscaSentinela(vetor, vetor[TAM_VETOR-2]);
	if( res != -1 )
		printf("\n\nValor %d encontrado na posicao %d.\n\n", vetor[res], res);
	else
		printf("\n\nValor não encontrado no vetor\n\n");

	return 0;
}