Senhor

Busca sequencial: a busca sequencial demonstrou o pior desempenho em todas as tentativas, o motivo é o tamanho das entradas e a quantidade de comparações efetuadas, a busca sequencial compara um a um de forma linear. A única forma de seu desempenho superar as outras formas de busca seria a ocasião de o valor buscado estar bastante próximo do ponto de partida da busca, de modo que seja pequeno o numero de comparações, ou seja, a diferença entre o ponto de partida e a posição do valor buscado seja pequena.

Busca interpolada: a busca interpolada superou, em desempenho, apenas a busca sequencial. O motivo é também o tamanho da entrada, dadas as entradas sugeridas a quantidade de comparações é consideravelmente menor usando as chaves e as alterações de posições do ponteiro. A única forma de seu desempenho superar a busca binaria seria a ocasião de o valor buscado esteja posicionado em alguma das primeiras chaves criadas (um bom caso, próximo do melhor caso), o desempenho da busca depende também da boa distribuição das chaves no vetor.

Busca Binaria: O modo como o vetor foi organizado favorece imensamente a busca binaria, valores ordenados e com entradas grandes, busca binaria diminui visivelmente a quantidade de comparações. A cada comparação a busca binaria elimina metade do range de busca. É imbatível na ocasião de os seus concorrentes não encontrarem ótimos casos no posicionamento do valor buscado e em casos de entradas grandes.

Conclusão:
Fica claro que o que define a performance da busca de valores dentro de um vetor é a quantidade de comparações a que os valores são submetidos. Dentre as opções utilizadas cada uma possui um nível de complexidade e deve ser aplicada a cada caso. No caso de busca linear ou sequencial, para obter ótima performance o vetor não deve possuir muitas posições, nesse caso as comparações são minimizadas. No caso da busca por interpolação a criação das chaves é feita e as comparações feitas por blocos menores que na busca