Adicionar implementação do algoritmo de Busca Interpolada (Interpolation Search)

[mateushsx]

A Busca Interpolada (Interpolation Search) é uma melhoria da busca binária, aplicável a arrays ordenados. Ela usa a posição do valor de busca para melhorar a eficiência. É particularmente eficiente quando os elementos do array estão uniformemente distribuídos.

Tarefas:

• Implementar o algoritmo em algorithms/searching/interpolation-search/index.js.
• Criar a documentação do algoritmo em algorithms/searching/interpolation-search/README.md, incluindo:
  • Descrição do funcionamento do algoritmo.
  • Exemplo de código com uma breve explicação.
  • Análise de complexidade temporal e espacial.

Complexidade:

• Tempo: O(log log n) no melhor caso; O(n) no pior caso.
• Espaço: O(1).