Descrição indutiva: Busca sequencial recursiva em Java

Neste post, vamos implementar em Java e descrever indutivamente um algoritmo que realiza a busca sequencial em um vetor. Apresentaremos uma implementação recursiva, em outro post trataremos da implementação iterativa.

Descrição indutiva:

• Caso Base: Trivial, não fazemos busca em listas vazias.
• Hipótese de Indução: Vamos supor que a hipótese de indução busca um valor em uma lista com n-1 elementos.
• Caso Geral: Simples, verificamos se o último elemento é o valor procurado, se não for entregamos os n-1 primeiros elementos para a hipótese de indução que se encarrega de fazer a busca no resto da lista.

Agora, apresentaremos uma implementação que decorre da descrição indutiva apresentada acima.

• Implementação em Java:

public class LinearSearch {

 public static int linearSearch(int vet[], int n, int value) {

  if (n >= 0) {
   if (vet[n] == value)
    return n;
   else
    return linearSearch(vet, n - 1, value);
  }
  return -1;
 }

 public static void main(String[] args) {

  int vet[] = { 10, 2, 43, 14, 25, 6, 37 };
  int value = 14;
  int index = linearSearch(vet, 6, value);

  if (index == -1)
   System.out.println("Elemento não encontrado");
  else
   System.out.println("O índice do elemento " + value + " é: " + index);
 }
}

Complexidade do algoritmo/implementação:

Usando indução não é difícil encontrar uma relação de recorrência que expresse o tempo de execução do algoritmo acima. O raciocínio é simples, basta imaginar que o tempo total do algoritmo é o tempo que gastamos para verificar se o último elemento é o procurado, mais o tempo que a hipótese de indução gastou para procurar nos n-1 elementos restantes, ou seja, T(n) = T(n-1) + O(1). Resolvendo a recorrência, temos

                                                                  T(n) = T(n-1) + O(1)

                                                                  T(n) = T(n-2) + 1 + 1

                                                                  T(n) = T(n-3) + 1 + 1 + 1

                                                                  T(n) = T(n-4) + 1 + 1 + 1 + 1 + 1

                                                                  ...

                                                                  T(n) = T(0) + 1 + 1 + 1 + ... + 1

                                                                  T(n) = O(n)

Analisando a relação de recorrência, podemos perceber que a busca sequencial possui complexidade linear, o algoritmo visita cada elemento apenas uma vez.

Como sempre, utilizamos a Indução Matemática para descrever nossos problemas. Para o iniciante que não está acostumado com esta abordagem, pode parecer confuso no início, mas nada que a prática não resolva.

Seguir @inductioncode