Sou iniciante/estudante em linguagem C e estou aprendendo sobre buscas. Estou tendo dificuldades de compreender sobre a busca interpolada, pois o código teste me passado na disciplina apresenta erro no cálculo da busca.
meio = menor + (maior-menor) * ((arg - vet[menor]) / vet[maior] - vet[menor]);
Encontrei um cálculo que apresenta resultado correto, mas apenas quando a tabela não possui números repetidos:
meio = menor + ((maior-menor)/(vet[maior]-vet[menor]))*(arg-vet[menor])
A dúvida se busca interpolada funciona em arranjo com números repetidos? Não encontrei respostas para essa dúvida sobre valores repetidos em buscas, e testando o código no Dev C++ apresenta erro quando existem números repetidos no arranjo de busca interpolada.
//Função de busca por interpolação
int buscaInterpol(int vec[5], int tam, int arg){
int menor, maior, meio, achou;
menor = 0;
maior = tam-1;
achou = -1;
while((menor <= maior) && (achou == -1)){
meio = menor + ((maior-menor)/(vec[maior]-vec[menor]))*(arg-vec[menor]);
if (arg == vec[meio]){
achou = meio;
}
if(arg < vec[meio]){
maior = meio - 1;
}
else {
menor = meio + 1;
}
}
return(achou);
}