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:
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 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.
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
Se conhecerem a «Big O Notation» esta sub-secçã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 , 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).
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 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».
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.
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 pseudo-có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)
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 .
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.
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.