Algoritmos de Pesquisa

Hoje vou falar sobre um tema que provavelmente já todos ouviram falar e que até, provavelmente, já precisaram de implementar em algum programa/script que fizeram. Vamos falar sobre os vários tipos de pesquisa que existem. Neste artigo vamos falar de:

• Pesquisa Linear
• Pesquisa Binária

Problema Clássico

Vamos começar por um problema simples. Dado um conjunto de números S com N elementos procurar nesse conjunto um número K. Se K \(\in\) S então imprimimos a posição em que K se encontra, noutro caso imprimimos uma mensagem que indica que K não pertence a S. Ora bem, este problema tem uma simples resolução. Percorremos S do início até ao final e em cada passo verificámos se o elemento que estamos a percorrer no momento é igual a K. Se for saímos do ciclo, se não for continuámos para o próximo elemento. Isto é chamada a pesquisa linear. Vou apresentar a seguir as diversas maneiras de resolver o problema e apresentar as características de cada solução.

Pesquisa Linear

A solução que apresentei anteriormente tem o nome de Pesquisa Linear. Vamos agora apresentar algumas características.

Este algoritmo cresce linearmente, ou seja, a cada passo o número de operações vai ser igual à quantidade de elementos que o conjunto tem. Ora bem, se vocês pegarem na vossa calculadora gráfica e meterem a função f(x) = x podem ver o crescimento da função que é, como já disse, linear.

Como já referi, a ideia desta função passa por fazer um ciclo de 1 até N (N é o número de elementos que o conjunto tem) e em cada passo no ciclo (a cada iteração) verificar se o elemento actual é igual a K.

Em pseudo-código:

array[1..N]
K = input ()

para i = 1 até N:
  se array[i] == K:
    imprimir (i)
    sair_do_ciclo

Em C++:

#include <cstdio>
#define MAX 100000000

using namespace std;

int array[MAX];

int find_in_array (int N, int K)
{
   for (int i = 0; i < N; i++)
      if (array[i] == K)
         return i;

   return -1;
}

int main ()
{
   int N = 0, K = 0, pos = 0;

   scanf ("%d", &K);
   scanf ("%d", &N);

   for (int i = 0; i < N; i++)
      scanf ("%d", &array[i]);

   pos = find_in_array (N, K);

   if (pos < 0)
      printf ("Elemento não foi encontrado\n");
   else
      printf ("Elemento encontrado na posição %d\n", pos + 1);

   return 0;
}

Em Python:

#!/usr/bin/python

def find_in_list (lst, N, K):
   for i in range (N):
      if lst[i] == K:
         return i

   return -1

lst = []
K = int (raw_input ())
N = int (raw_input ())

for i in range (N):
   lst.append (int (raw_input ()))

pos = find_in_list (lst, N, K)

if pos < 0:
   print 'Elemento nao foi encontrado'
else:
   print 'Elemento encontrado na posicao', pos + 1

Em VB.NET:

Module Module1

    Dim dimension, number As Integer
    Dim list() As Integer

    Sub Main()
        Console.Write("Lista de N elementos. Introduza N: ")
        dimension = Console.ReadLine
        Array.Resize(list, dimension)
        For i As Integer = 1 To dimension
            Console.Write("Introduza " & i.ToString & "º elemento da lista: ")
            list(i - 1) = Console.ReadLine
        Next
        Console.Write("Procurar K na lista. Introduza K: ")
        number = Console.ReadLine
        Console.WriteLine()
        Dim position As Integer = FindInArray(list, number)
        If position > 0 Then
            Console.WriteLine("Valor encontrado na lista, na posição " & position.ToString)
        Else
            Console.WriteLine("Valor NÃO encontrado na lista.")
        End If
        Console.Write("Qualquer tecla para terminar. . .")
        Console.ReadKey(True)
    End Sub

    Function FindInArray(ByRef array() As Integer, ByVal k As Integer) As Integer
        For i As Integer = 1 To array.Length
            If array(i - 1) = k Then
                Return i
            End If
        Next
        Return 0
    End Function

End Module

Complexidade

Se conhecerem a «Big O Notation» esta subsecção de pesquisa linear não vai ser difícil de entender. Já disse que o crescimento da função é linear e que o número de operações vai ser sempre igual à quantidade de elementos do conjunto. Para terem mais informações sobre a função que pode representar este algoritmo sigam este link: http://www.wolframalpha.com/input/?i=y+%3D+x.

Isto tudo leva-nos a uma complexidade \(O(N)\), em que N é a quantidade de elementos do conjunto.

Vamos agora, utilizando o exemplo que dei em C++, ver os tempos de execução para vários casos. Em cada caso vamos ver o N a crescer e vamos analisar consequentemente o crescimento do tempo também. Nota: Retirei a leitura dos dados e inicializei-os mesmo com um ciclo (para aumentar a eficiência).

• \(N = 10^1 \rightarrow T = 0.006s\)
• \(N = 10^2 \rightarrow T = 0.006s\)
• \(N = 10^3 \rightarrow T = 0.007s\)
• \(N = 10^4 \rightarrow T = 0.008s\)
• \(N = 10^5 \rightarrow T = 0.013s\)
• \(N = 10^6 \rightarrow T = 0.067s\)
• \(N = 10^7 \rightarrow T = 0.468s\)
• \(N = 10^8 \rightarrow T = 2.290s\)

Este último tempo já nem passa em concursos de programação como as ONI, por exemplo. Podemos então ver que o crescimento a nível de tempo desta função é grande. Se estivéssemos a trabalhar com outros tipos de dados, como strings, ainda era pior visto que tínhamos que percorrer todos os elementos e em cada passo comparar a string que queremos encontrar com a actual.

A complexidade deste último caso seria \(O(N * MAXLEN)\) onde MAXLEN é o tamanho máximo das strings.

Este tipo de pesquisa é útil quando sabemos que vamos ter poucos elementos no conjunto e quando não podemos/queremos perder muito tempo a implementar algo mais avançado e sofisticado. No entanto, para concursos de programação, onde os limites costumam ser altos propositadamente, esta pesquisa linear não chega. Na secção a seguir vamos ver uma outra pesquisa chamada «Pesquisa Binária».

Pesquisa Binária

Como vimos anteriormente a Pesquisa Linear não é suficiente visto que o tempo que demora para valores muito grandes também vai ser muito grande.

Temos outro algoritmo de pesquisa que nos vai diminuir muito o nosso tempo de execução. É chamada «Pesquisa Binária». Para podermos utilizar esta técnica, o conjunto que temos que utilizar tem que estar ordenado. Neste caso vou considerar que o conjunto está ordenado por ordem crescente. Todos os exemplos vão ser baseados nisso.

A ideia desta técnica é a cada passo dividir o conjunto em dois (daí se chamada pesquisa binária) e verificar em que lado se encontra a nossa resposta. Vamos imaginar que queremos procurar no conjunto {1, 2, 3, 4, 5} o elemento 5. Como disse, dividimos a nossa lista em metade (vamos ao elemento do meio - que neste caso é o que se encontra na posição 3 (começando a partir do 1)) e vemos em que lado está a resposta, isto é, se o elemento do meio for menor do que o elemento que queremos procurar então a nossa resposta encontra-se no lado direito do nosso conjunto, se fosse maior então a nossa resposta encontrava-se no lado esquerdo. Como é simples de perceber, isto só funciona se o conjunto estiver ordenado.

O que muitas vezes as pessoas que veem pela primeira vez esta técnica pensam é que apenas dividimos o nosso conjunto uma vez, ou seja, que percorríamos metade do nosso conjunto. Isto é falso. Aliás, se assim fosse o melhoramento do tempo não era muito e não nos adiantava implementar este algoritmo. A ideia é ir dividindo sempre o conjunto até apenas nos restar um único elemento. Vamos a um exemplo.

• S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
• K = 11

Vamos agora representar mais ou menos a resolução com pesquisa binária. S é o conjunto e M' é o elemento do meio do conjunto actual.

1- S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
   M' = 6
   6 < 11, logo a nossa resposta está no lado direito

2- S = {7, 8, 9, 10, 11}
   M' = 9
   9 < 11, logo a nossa resposta está no lado direito

3- S = {10, 11}
   M' ~ 10
   10 < 11, logo a nossa resposta está no lado direito

4- S = {11}
   M' = 11
   11 = 11, logo 11 existe no conjunto

Como podem ver a quantidade de passos que precisámos é muito pouco comparando com a pesquisa linear. Para verem o crescimento do algoritmo metam na vossa calculadora gráfica a seguinte função: f(x) = log(x) / log(2).

Vamos ver então o algoritmo em pseudocódigo:

array[1..N]
K = input ()

low = 1, high = N

enquanto low <= high:
   i = (low + high) / 2

   se array[i] < K:
      low = i + 1
   noutro caso:
      high = i - 1

se array[i] == K:
  imprimir(i)
noutro caso:
  imprimir('Nao existe')

Em C++:

#include <cstdio>
#define MAX 100000000

using namespace std;

int array[MAX];

int binary_search (int N, int K)
{
        int low = 0, high = N - 1, middle = 0;

        while (low <= high)
        {
                middle = (low + high) / 2;

                if (array[middle] < K)
                        low = middle + 1;
                else if (array[middle] > K)
                           high = middle - 1;
                     else
                           break;
        }

        if (array[middle] == K)
                printf ("Elemento existe na posição %d\n", middle + 1);
        else
                printf ("Não existe\n");
}

int main ()
{
        int N = 0, K = 0;

        scanf ("%d %d", &N, &K);
        for (int i = 0; i < N; i++)
                scanf ("%d", &array[i]);

        binary_search (N, K);

        return 0;
}

Em Python:

#!/usr/bin/python

def binary_search (lst, N, K):
    while low <= high:
        middle = (low + high) / 2

        if lst[middle] < K:
            low = middle + 1
        else:
            high = middle - 1

    if lst[middle] == K:
        print 'Posicao', middle + 1
    else:
        print 'Nao existe'

lst = []
K = int (raw_input ())
N = int (raw_input ())

for i in range (N):
   lst.append (int (raw_input ()))

binary_search (lst, N, K)

Complexidade

O tempo de execução para N = 10^8 é de 1.040s. Portanto, podemos concluir que a pesquisa binária é muito mais rápida do que a pesquisa linear.

Esta pesquisa binária tem uma complexidade de \(O(log_2 N)\).

A cada passo dividimos o conjunto em duas partes e escolhemos a parte em que se vai encontrar a nossa resposta. Isto leva-nos a uma complexidade logarítmica binária.

Para verem melhor o crescimento da função deixo aqui esta imagem.

Conclusão

Pelas complexidades podemos concluir que a pesquisa binária é mais rápida do que a pesquisa linear (bastante mais). Quando queremos apenas fazer uma pesquisa e não temos o conjunto já ordenado é melhor utilizar a pesquisa linear visto que qualquer ordenação vai ser mais lenta do que a pesquisa linear. No entanto, quando queremos fazer várias pesquisas é sem dúvida melhor ordenarmos o conjunto e depois utilizarmos a pesquisa binária para as pesquisas.

Tenho mais uma nota a deixar. Todos os tempos de execução dados neste artigo podem não ser _apenas_ da parte da pesquisa binária porque o preenchimento dos arrays também contam (e bem), logo não podemos considerar que para N = 10⁸ o tempo de execução de uma pesquisa binária é mesmo ~1s mas é muito menos. O tempo de preenchimento é que faz com que o tempo de execução seja maior. Podem também utilizar os dois algoritmos com strings e comparar os tempos de execução (neste caso a diferença entre os dois vai ser muito maior) e para verem como é diferente não precisam de ter um N muito grande.