Estrutura de dados - Pesquisa de interpolação

A pesquisa de interpolação é uma variante aprimorada da pesquisa binária. Este algoritmo de pesquisa funciona na posição de sondagem do valor necessário. Para que esse algoritmo funcione corretamente, a coleta de dados deve ser ordenada e igualmente distribuída.

A pesquisa binária tem uma grande vantagem de complexidade de tempo sobre a pesquisa linear. A pesquisa linear tem complexidade de pior caso de Ο (n), enquanto a pesquisa binária tem Ο (log n).

Existem casos em que a localização dos dados alvo pode ser conhecida com antecedência. Por exemplo, no caso de uma lista telefônica, se quisermos pesquisar o número de telefone de Morphius. Aqui, a pesquisa linear e até a pesquisa binária parecerão lentas, pois podemos pular diretamente para o espaço da memória onde os nomes que começam com 'M' são armazenados.

Posicionamento na pesquisa binária

Na pesquisa binária, se os dados desejados não forem encontrados, o restante da lista é dividido em duas partes, inferior e superior. A busca é realizada em qualquer um deles.

Mesmo quando os dados são classificados, a pesquisa binária não aproveita para sondar a posição dos dados desejados.

Sondagem de posição na pesquisa de interpolação

A pesquisa de interpolação encontra um item específico calculando a posição da sonda. Inicialmente, a posição da sonda é a posição do item mais central da coleção.

Se ocorrer uma correspondência, o índice do item será retornado. Para dividir a lista em duas partes, usamos o seguinte método -

mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

where −
   A    = list
   Lo   = Lowest index of the list
   Hi   = Highest index of the list
   A[n] = Value stored at index n in the list

Se o item do meio for maior do que o item, a posição da sonda é calculada novamente na submatriz à direita do item do meio. Caso contrário, o item é pesquisado na submatriz à esquerda do item do meio. Este processo continua na submatriz também até que o tamanho da submatriz seja reduzido a zero.

A complexidade do tempo de execução do algoritmo de pesquisa de interpolação é Ο(log (log n)) em comparação com Ο(log n) do BST em situações favoráveis.

Algoritmo

Como é uma improvisação do algoritmo BST existente, estamos mencionando as etapas para pesquisar o índice de valor de dados 'alvo', usando sondagem de posição -

Step 1 − Start searching data from middle of the list.
Step 2 − If it is a match, return the index of the item, and exit.
Step 3 − If it is not a match, probe position.
Step 4 − Divide the list using probing formula and find the new midle.
Step 5 − If data is greater than middle, search in higher sub-list.
Step 6 − If data is smaller than middle, search in lower sub-list.
Step 7 − Repeat until match.

Pseudo-código

A → Array list
N → Size of A
X → Target Value

Procedure Interpolation_Search()

   Set Lo  →  0
   Set Mid → -1
   Set Hi  →  N-1

   While X does not match
   
      if Lo equals to Hi OR A[Lo] equals to A[Hi]
         EXIT: Failure, Target not found
      end if
      
      Set Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo]) 

      if A[Mid] = X
         EXIT: Success, Target found at Mid
      else 
         if A[Mid] < X
            Set Lo to Mid+1
         else if A[Mid] > X
            Set Hi to Mid-1
         end if
      end if
   End While

End Procedure

Para saber sobre a implementação da busca de interpolação na linguagem de programação C, clique aqui .