Interpolated search in C, repeated values in the array
I Am A Beginner / student in C language and I am learning about searches. I am having difficulty understanding about interpolated search, because the code test me passed in the discipline presents error in the calculation of the search.
meio = menor + (maior-menor) * ((arg - vet[menor]) / vet[maior] - vet[menor]);
I found a calculation that presents correct result, but only when the table has no repeated numbers:
meio = menor + ((maior-menor)/(vet[maior]-vet[menor]))*(arg-vet[menor])
The question if interpolated search works in arrangement with repeated numbers? I did not find answers to this doubt about repeated values in searches, and testing the code in Dev C++ presents error when there are repeated numbers in the interpolated search arrangement.
//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);
}
1 answers
Dude, your code seems almost correct to me, with few points to be right:
* First, when declaring the function, instead of int vec[5] you should use int *vec, which would hold arrays of any size. Keep in mind that when you pass an array to a function, what the function receives as an argument is actually a pointer to the first element of the array, not the array itself.
* Then, no matter if there are repeated elements or not, the array passed as argument it must be ordered. If it's not, it could be a mistake.
• Also, to avoid division by zero, before calculating the value of meio in each iteration, you should test if arg == vec[menor] (in this case, you have found the element, and can already Return menor.
Note that if the array is ordered, you don't need to test if vec[maior] != vec[menor], because the only chance for this to happen is if arg == vec[menor], which you would have tested before (think a little to see this!).
In short, what missing from your code is to add, at the beginning of while, and before assigning to the variable meio, the following snippet:
if( arg == vec[menor] )
return menor;
By the way, I would dismiss the variable achou, and use return where you assign to that variable, i.e. in if( arg == vec[meio] ). At the end, after while, instead of returning achou you can return -1 straight, as it is certain that the element will not have been found in the array.