Interpolated search in C, repeated values in the arrangement

Question

I’m a beginner/student in C language and I’m learning about search. I’m having difficulty understanding about the interpolated search, because the test code I 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 does not have repeated numbers:

meio = menor + ((maior-menor)/(vet[maior]-vet[menor]))*(arg-vet[menor])

The doubt if interpolated search works in arrangement with repeated numbers? I did not find answers to this question about repeated values in searches, and testing the code in Dev C++ shows error when there are repeated numbers in the interpolated search array.

//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);
}

Answer 1

Man, your code seems almost right to me, with few points to be hit:

• First, when declaring the function, instead of int vec[5] you should use int *vec, which would hold arrays of any size. Remember that when you pass an array to a function, what the function takes as an argument in reality is a pointer to the first element of the array, not the array itself.
• Then, whether or not there are repeated elements, the array passed as argument must be sorted. If it is not, it may even give error.
• In addition, to avoid dividing by zero, before calculating the value of meio in each iteration, you should test whether arg == vec[menor] (in this case, you have found the element, and can already return menor.

Note that if the array is ordered, you do not need to test if vec[maior] != vec[menor], because the only chance for that to happen is if arg == vec[menor], what you would have tested before (think about it a bit!).

In short, what your code lacks is to add at the beginning of the while, and before being assigned to the variable meio, the following excerpt:

if( arg == vec[menor] )
    return menor;

By the way, I would waive the variable achou, and would use return where you assign this variable, that is, in if( arg == vec[meio] ). At the end, after the while, instead of returning achou you can return -1 directly, as it is certain that the element will not have been found in the array.