0

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

1 Resposta 1

0

Cara, seu código me parece quase correto, com poucos pontos a serem acertados:

• Primeiro, ao declarar a função, ao invés de int vec[5] você deveria usar int *vec, o que comportaria arrays de qualquer tamanho. Lembre-se de que, quando você passa um array para uma função, o que a função recebe como argumento na realidade é um ponteiro para o primeiro elemento do array, não o array em si.
• Depois, não importando se há ou não elementos repetidos, o array passado como argumento deve estar ordenado. Se não estiver, pode mesmo dar erro.
• Além disso, para evitar a divisão por zero, antes de calcular o valor de meio em cada iteração, você deveria testar se arg == vec[menor] (neste caso, você achou o elemento, e já pode retornar menor.

Repare que, se o array estiver ordenado, você não precisa testar se vec[maior] != vec[menor], pois a única hipótese para isso acontecer é se arg == vec[menor], o que você já teria testado antes (pense um pouco para constatar isso!).

Em suma, o que falta a seu código é adicionar, no início do while, e antes da atribuição à variável meio, o seguinte trecho:

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

Por sinal, eu dispensaria a variável achou, e usaria return onde você atribui a essa variável, ou seja, no if( arg == vec[meio] ). Ao final, depois do while, ao invés de retornar achou você pode retornar -1 direto, pois é certo que o elemento não vai ter sido encontrado no array.

2
  • Opa valeu pela aula. Mas algo que não compreendi ainda, ordenação é obrigatório em todo algoritmo de busca, para operar corretamente? Ou é característica individual de cada algoritmo de busca, podendo operar sem ordenação?
    – Santon
    Commented 2/07/2020 às 1:12
  • É algo que depende das características de cada algoritmo. Mas imagine como é no mundo real, fora do digital: é mais fácil para você encontrar algo que você procura em meio a uma bagunça, ou quando as coisas já têm algum tipo de arrumação? Da mesma forma, os algoritmos de busca genéricos são menos eficientes que aqueles que assumem que os dados estão arrumados, seja ordenados, ou com algum outro tipo de arrumação. Commented 19/07/2020 às 16:57

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .