Estrutura de Dados - Pesquisa - Sequencial ou Linear, Binária e Interpolação

PESQUISA

Nos dias de hoje, o acesso rápido a informação pode ser determinante para o sucesso do aplicativo. Por isso o algoritmo de pesquisa é tão importante quanto a estrutura de armazenamento e o algoritmo de ordenação.

PESQUISA SEQUENCIAL

Vamos falar do mecanismo de pesquisa mais trivial que existe, a Pesquisa Linear ou Sequencial.

Esse algoritmo consiste em percorrer cada um dos elementos da nossa estrutura até encontrar o elemento desejado. Sua eficiência é inversamente proporcional a quantidade de elementos que tivermos que percorrer. Na melhor hipótese o elemento desejado será o primeiro e na pior hipótese o elemento desejado será o último.

Podemos melhorar significativamente o desempenho se os elementos estiverem ordenados. Por isso é tão importante escolher a estrutura certa assim como aplicar algoritmos de ordenação.

Por exemplo, se queremos encontrar um nome específico na nossa agenda telefônica, será muito mais rápido se a agenda estiver organizada por ordem alfabética. Assim podemos pular alguns nome que temos certeza que não irão atender ao critério de pesquisa.

public class PesquisaLinear {

 public static int pesquisar(String arr[], String argumento) {
  
  for (int i = 0; i < arr.length; i++) {
   if (arr[i] == argumento) {
    return i;
   }
  }

  return -1;
 }

 public static void main(String args[]) {
  String arr[] = { "A", "B", "C", "D" };
  System.out.println(pesquisar(arr, "C"));
 }

}

PESQUISA BINÁRIA

A pesquisa binária utiliza da técnica "dividir para conquisar". Consiste em dividir os elementos ao meio, em seguida é verificado se o elemento desejado é maior ou menor que o elemento central. Caso seja maior, então o elemento desejado obrigatoriamente deve estar do lado direito da divisão e caso seja menor então obrigatoriamente deve estar do lado esquerdo. Esse processo de divisão e verificação é repetido até encontrar o elemento.

Repare para que esse algoritmo funcione, os elementos devem estar obrigatoriamente ordenados, caso contrário pode não funcionar.

public class PesquisaBinaria {

 public static int pesquisar(int arr[], int l, int r, int x) {
  if (r >= l) {
   int mid = l + (r - l) / 2;

   if (arr[mid] == x)
    return mid;

   if (arr[mid] > x)
    return pesquisar(arr, l, mid - 1, x);

   return pesquisar(arr, mid + 1, r, x);
  }

  return -1;
 }

 public static void main(String args[]) {
  int arr[] = { 2, 3, 4, 10, 40 };
  int n = arr.length;
  int x = 10;
  int posicao = pesquisar(arr, 0, n - 1, x);
  if (posicao == -1)
   System.out.println("Elemento não encontrado");
  else
   System.out.println("Elemento encontrado na posição " + posicao);
 }
}

PESQUISA POR INTERPOLAÇÃO

Este algoritmo de pesquisa, assim como a busca binária, tem como premissa que os elementos esteja previamente ordenados, além disso o algoritmo é semelhante a busca binária, eles diferem na forma como os elementos são divididos. Enquanto a busca binária está sempre dividindo ao meio, a busca por interpolação divide os elementos com base na fórmula abaixo:

pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]

public class PesquisaInterpolacao {

 public static int pesquisar(int[] arr, int x) {
  int lo = 0, hi = (arr.length - 1);

  while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {

   if (lo == hi) {
    if (arr[lo] == x)
     return lo;
    return -1;
   }

   int pos = lo + (((hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]));

   if (arr[pos] == x)
    return pos;

   if (arr[pos] < x)
    lo = pos + 1;

   else
    hi = pos - 1;
  }
  return -1;
 }

 public static void main(String[] args) {
  int x = 18;
  int arr[] = new int[] { 10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47 };
  int posicao = pesquisar(arr, x);

  if (posicao != -1)
   System.out.println("Elemento encontrado na posição " + posicao);
  else
   System.out.println("Elemento não encontrado.");
 }

}