Métodos de Pesquisa

Luiz Arão Carvalho ¹ <maximusmano@gmail.com>

Universidade Federal do Tocantins (UFT) – Curso de Ciências da Computação – Campus Palmas Av: NS 15 ALC NO 14, 109 Norte ,CEP 77001-090 – Palmas - TO

esumo

Este artigo aborda algumas características entre alguns dos mais conhecidos e

usados métodos de pesquisa, a seqüencial e a binária, mostrando as diferenças e

semelhança entre estes.

Palavras-chave: Métodos de pesquisa, pesquisa binária, pesquisa seqüencial.

1. INTRODUCAO

Uma das tarefas mais habituais na programação é a pesquisa de informações, o que exige o

desenvolvimento de algoritmos eficientes de pesquisa [1] Neste trabalho discutiremos um pouco

sobre métodos de pesquisa seqüencial e binária.

Essas técnicas também são conhecidas como algoritmos de busca. Em ciência da

computação, um algoritmo de busca, em termos gerais, é um algoritmo que toma um problema

como entrada e retorna a solução para o problema, geralmente após resolver um número possível de

soluções. A maioria dos algoritmos estudados por cientistas da computação que resolvem

problemas são algoritmos de busca. O conjunto de todas as soluções possíveis para um problema é

chamado de espaço de busca [2].

Alguns tipos de pesquisa necessitam que haja uma organização da informação, como é o

caso da pesquisa binária, então para efeito de estudo desse método foi estudados alguns métodos de

ordenação e por fim escolhido o mais apropriado para nosso a abordagem, o quick sort. Nesse artigo então falaremos sobre a pesquisa seqüencial(ou linear) e a busca binária,

mostrado características de ambas, situações onde diferem, como essas são implementadas alguns

resultados obtidos com testes de cada uma.

1.1. PESQUISA SEQUENCIAL.

Pesquisa seqüencial ou busca linear é um tipo de pesquisa em vetores ou listas que

ocorre de modo seqüencial, ou seja, elemento por elemento, assim a função do tempo em

relação ao número de elementos é linear, ou seja, cresce proporcionalmente. Algo

importante a se ressaltar é a necessidade de que o vetor no qual se deseja realizar a pesquisa

esteja, de alguma maneira, ordenado. Por realizar muitas comparações e buscar um resultado

de maneira bruta, essa não é considerada a pesquisa mais eficiente, mas pode ser aplicada

em vários casos sem nenhum tipo de prejuízo.

Como dito essa técnica possui um custo de processamento linear, ou seja, seu custo

aumenta de acordo com o tamanho da entrada e o posicionamento do elemento a se r

encontrado. Tendo isso em mente podemos afirmar que o melhor caso para nosso algoritmo

seria encontrar o elemento na primeira comparação (na primeira posição do nosso vetor), já

o pior caso aconteceria se esse elemento estivesse na ultima posição, realizando assim N

comparações, sendo N o numero de elementos em nosso vetor , já em um possível caso

médio seria uma busca por qualquer elemento entre o ultimo e o primeiro.

R

1.1.1. Implementação

Com o objetivo de tornar as funções, o mais versátil possível, elas têm uma variável

de entrada que indica o índice do vetor onde deve começar a pesquisa. As funções calculam

e devolvem o índice do elemento onde está armazenado o valor procurado. Podemos

observar isso melhor com o algoritmo abaixo:

Função procura(vetor, elementoProcurado)

inicio

para cada elemento do vetor, até que o vetor acabe, faça

se elementoDoVetor for igual ao elementoProcurado

Retorne a posicaoDoVetor

Fim do se

Fim do Para

Informe que elementoProcurado não foi encontrado se não o achar

Fim da função procura

Algoritmo 1: Pesquisa Seqüencial

Para demonstrar o real funcionamento do algoritmo foi implementado o seguinte

código em ruby:

Figura 1: Classe da Pesquisa Sequencial

busca_sequencial(vetor,elemento) é o método que realiza essa tarefa, onde vetor e

elemento são respectivamente o vetor de elementos a ser feita a busca e o elemento a ser

buscado. Logo a frente uma variável de instancia chamada @result, é inicializado com um

hash para que possa guardar o resultado da busca, essa estrutura é composta de :pos, que

guarda a posição do elemento, :iter que indica a quantidade de iterações realizadas e

:valor, a titulo de informação, permanece com o valor buscado.

A partir daí temos um bloco onde pegamos cada elemento (linha 11 a 14)

comparamos se este é igual ao elemento buscado se não ele prossegue sempre a cada

comparação aumenta o valor do índice de iterações e de posicionamento no vetor. Caso não

encontremos o elemento retornamos o vetor sem a posição.

1.2. BUSCA BINARIA.

A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é

um algoritmo de busca em vetores que requer acesso aleatório aos elementos do mesmo. Ela

parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de

busca (Divisão e conquista) comparando o elemento buscado (chave) com o elemento no

meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso.

Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca

continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da

chave, à busca continua na metade anterior do vetor. [3].

1.2.1. Implementação

Para melhorar nosso entendimento sobre a busca binária abaixo, Algoritmo 1, temos

o algoritmos que mostra a estratégia da busca binária:

Função procura(vetor, elementoProcurado)

inicio

maximo recebe inicio do vetor

mínimo recebe fim do vetor

meio recebe maximo mais mínimo dividido por 2

enquato mínimo menor maximo

se meio for igual ao elementoProcurado

Retorne a meio

Se não, se elementoProcurado menor que meio

maximo recebe meio menos 1

se não

mínimo recebe meio mais 1

Fim do se

Fim do enquanto

Informe que elementoProcurado não foi encontrado se não o achar

Fim da função procura

Algoritmo 2: Pesquisa Binária

Novamente implementamos uma função para que possamos ver esse algoritmo em

ação, o seguinte método foi implementado em ruby:

O método busca binária necessita de três variáveis de paramentos vetor,

elemento e ordenar, que são, consecutivamente, o vetor de elementos, o elemento a ser

procurado e um booleano que indica se deve ou não ser feita a ordenação do vetor.

Inicializamos então, na linha 37 a variável inf(limite inferior) com zero, pois é o

primeiro índice de nosso vetor, logo após inicializamos sup(limite superior) com o tamanho

do vetor menos um, e uma variável @result, que é o conjunto de solução que comporta a

posição do elemento encontrado, a quantidade de comparações que foi realizada para esse

feito e o valor do elemento procurado. Na linha 41 verificamos a necessidade de ordenação

do vetor e a efetuamos se verdadeira.

Da linha 43 á 53, temos um loop onde realizamos comparação entre inf e sup para

finalizar nossas comparações, incrementamos o numero de it erações e definimos a posição

do elemento a ser comparado com o elemento procurado como sendo a metade do nosso

vetor, ai então verificamos que naquela posição(meio do vetor) se encontra o elemento

buscado se não, verificamos se esse elemento é menor que o elemento do meio do vetor se

isso for verdade, então definimos o limite superior do vetor como o índice do meio menos 1.

Se o elemento buscado for maior fazemos o inverso, o limite inferior se torna então o indice

mediano mais 1.

Se após isso não encontrarmos o elemento definimos a posição como nula e

retornamos o resultado

2. RESULTADOS

Para efetuar uma comparação entre os dois métodos de busca, em questão de

complexidade será utilizada a notação O grade (Big O).

Para um vetor com N elementos, o pior caso da pesquisa seqüencial é quando o valor

procurado está no ultimo elemento do vetor ou não existe naquele conjunto, o que exige a

análise dos N elementos do vetor. Se considerarmos ainda, que a probabilidade do valor

procurado estar em qualquer um dos elementos do vetor é igual, então a pesquisa seqüencial

analisa em média N elementos. Se considerarmos que a probabilidade do valor não existir

no vetor é igual a ser qualquer um dos elementos desse conjunto, então a pesquisa

seqüencial analisa em média N+1 elementos. Portanto, a eficiência do algoritmo de pesquisa

seqüencial é de ordem O(N).

Para o mesmo vetor, o pior caso da pesquisa binária é quando se reduz o intervalo em

análise a apenas um elemento do vetor, o que exige a análise de log2(N+1) elementos do

vetor. Portanto, podemos definir a eficiência do algoritmo de pesquisa binária é de ordem

O(log2 N).

Partindo desses resultado então podemos afirmar que o método binário, com um

conjunto suficientemente grande de elementos, é mais vantajoso que o seqüencial, caso

nosso vetor esteja ordenado, caso o vetor não esteja ordenado isso se inverte. Por exemplo

se utilizamos o método quick sort para ordenar o vetor antes do processo de busca binária

teríamos O(log2 N) + O(N²), ou seja, nosso algoritmo agora teria complexidade O(N²), bem

maior que a O(N) do método seqüencial.

Foram realizados então testes utilizando cada um dos métodos aqui mostrados para

verificar essas afirmações:

2.1.1. Testes com Vetor Ordenado

O Elemento 499999 foi encontrado na Posição 499999, com 1 iterações O Elemento 999999 foi encontrado na Posição 999999, com 20 iterações O Elementos aleatório 746373 foi encontrado na posição 746373, com 17 iterações O Elementos aleatório 851150 foi encontrado na posição 851150, com 20 iterações O Elementos aleatório 562607 foi encontrado na posição 562607, com 19 iterações O Elementos aleatório 361931 foi encontrado na posição 361931, com 19 iterações O Elementos aleatório 200714 foi encontrado na posição 200714, com 18 iterações O Elementos aleatório 320341 foi encontrado na posição 320341, com 15 iterações O Elementos aleatório 651574 foi encontrado na posição 651574, com 18 iterações O Elementos aleatório 303724 foi encontrado na posição 303724, com 16 iterações O Elementos aleatório 609029 foi encontrado na posição 609029, com 17 iterações O Elementos aleatório 215504 foi encontrado na posição 215504, com 20 iterações

Resultado 1: Binário com vetor Ordenado

A primeira linha utilizamos o método de busca com a melhor solução possível, ou

seja para que ele ache na primeira iteração o elemento buscado, a segunda linha mostra o

inverso buscamos o elemento 999999, como ele é um elemento de extremidade ele será o

encontrado apenas na ultima iteração, tornando-se assim um exemplo de pior caso. As 10

linhas subseqüentes são números aleatórios que variam suas iterações.

Com esse resultado podemos observar o seguinte, o máximo de iterações que

necessitamos realiza par encontrar um elemento é vinte, isso realmente é muito pouco se

considerarmos a quantidade de elementos existentes no vetor (Um Milhão).

O Elemento 0 foi encontrado na Posição 0, com 1 iterações O Elemento 999999 foi encontrado na Posição 999999, com 1000000 iterações O Elemento aleatório 932076 foi encontrado na posição 932076, com 932077 iterações O Elemento aleatório 818878 foi encontrado na posição 818878, com 818879 iterações O Elemento aleatório 874453 foi encontrado na posição 874453, com 874454 iterações O Elemento aleatório 489119 foi encontrado na posição 489119, com 489120 iterações O Elemento aleatório 138820 foi encontrado na posição 138820, com 138821 iterações O Elemento aleatório 277097 foi encontrado na posição 277097, com 277098 iterações O Elemento aleatório 954754 foi encontrado na posição 954754, com 954755 iterações O Elemento aleatório 407988 foi encontrado na posição 407988, com 407989 iterações O Elemento aleatório 952064 foi encontrado na posição 952064, com 952065 iterações O Elemento aleatório 865820 foi encontrado na posição 865820, com 865821 iterações

Resultado 2: Pesquisa Seqüencial

Vemos então no Resultado 2 a diferença, se tratando de iterações, onde na pesquisa

binária realiza no máximo vinte iterações para um vetor de um milhão de posições, já a

pesquisa seqüencial realizará até um milhão de iterações caso o elemento esteja na ultima

posição.

Temos na primeira linha, desse segundo resultado, o melhor caso, que para esse

exemplo seria que o elemento buscado esteja na primeira posição do vetor, pois assim só

necessita de uma iteração para encontrá-lo. Na segunda linha obtivemos o pior caso, onde o

elemento buscado se encontra na ultima posição necessitando para o encontrar de um milhão

de interações.

As dez linhas seguintes representam casos médios realizados aleatoriamente,

observa-se que para encontrar os objetos são necessárias tantas interações quantos são os

elementos antecedentes a ele na ordem do vetor, isso proporciona um gasto computacional

bem grande caso o vetor possua extrema quantidade de elementos.

Então podemos afirmar que a busca binária é melhor que a busca seqüencial? Não,

ela é melhor empregada em certo tipo de situação , por exemplo para um numero pequeno de

elementos, 100 por exemplo, a diferença entre o tempo de processamento das duas é quase

inexistente. E o maior motivo para afirmar que a seqüencial pode ser ainda melhor que a

binária é a necessidade de que para a utilização da busca binária é necessário que o vetor de

elementos esteja ordenado. Caso não esteja o custo de ordenação pode ser bem maior que

uma busca seqüencial, para verificar essa possibilidade foram realizados testes com os

algoritmos implementados.

user system total real

Busca Seqüencial (Melhor caso):

0.000000 0.000000 0.000000 0.000000

Busca Seqüencial (Pior caso)

2.297000 0.000000 2.297000 2.329000

Busca Seqüencial (Casos Médios

10x)

11.640000 0.000000 11.640000 11.703000

Total 14.032.000 s Tabela 1: Bench Mark da busca Seqüencial

Na tabela 1 temos o resultado em Segundos das buscas realizadas a um vetor de um

milhão de posições, onde para o melhor caso o tempo de busca foi insignificante, chegando

a zero em nossa amostra, já para o pior caso chegamos a ter quase 2,3(em tempo de

processamento) segundos para percorrer todo o vetor em busca do elemento e pouco mais de

2,3 de tempo real. Para os casos médios chegamos a mais de 11,5 segundos, o que

caracteriza que entre pesquisas fáceis e mais complicadas tivemos uma média de pouco mais

de um segundo para cada pesquisa.

user system total real

Busca binária (Melhor caso):

0.000000 0.000000 0. 000000 0.000000

Busca binária (Pior caso)

0.000000 0.000000 0.000000 0.000000

Busca binária (Casos Médios

10x)

0.000000 0.000000 0.000000 0.000000

Total Tabela 2: Bench Mark Pesquisa Binária em vetor ordenado

Vemos aqui a eficiência de nossa busca binária, todos os tempos, tanto em pior

quanto melhor ou até mesmo o tempo de 10 buscas seguidas simulando um caso médio, não

chegou a alguma importância significante para o processamento de nossa busca.

Como dito anteriormente para que nossa busca binária funcione, o vetor de entrada

deve estar organizado previamente, caso essa ordenação não exista nosso algoritmo perde

sua eficiência vejamos a tabela 3 o resultado de buscas com ordenação.

Tabela 3: Busca Binária com ordenação

user system total real

Busca binária c/ Ordenação

(Melhor caso):

84.078000 0.188000 84.266000 84.796000

Busca binária c/ Ordenação (Pior

caso)

86.860000 0.140000 87.000000 87.047000

Busca binária c/ Ordenação

(Casos Médios 10x)

811.125000 1.657000 812.782000 816.063000

Total

Verificamos agora o custo que a ordenação do vetor realiza sobre o tempo de

processamento do algoritmo, foi utilizada para esse teste a ordenação com a técnica quick

sort, até mesmo para o melhor caso não há grande diferença, pois o custo de processamento

que realmente importa é o de ordenação.

3. CONCLUSÃO

Os métodos de busca são ferramentas de grande auxilio e que são comumente utilizadas em

diversas áreas não só da computação, o estudo desses métodos se faz necessário para a melhor

compreensão e melhor utilização desses métodos em problemas do dia a dia. Algo que deve ser

focado sempre é em quais situações determinado método é melhor que outro, pois não há um

método que seja ideal para qualquer que seja a situação, o estudo da complexidade é uma das

melhor formas de escolher essas técnicas para sua melhor funcionalidade.

REFERÊNCIAS BIBLIOGRÁFICAS

[1] Rocha, A, e Borges,(2000) A. Programação Estruturas de dados e algoritmos em C,

Departamento de Eletrônica e Telecomunicações, Universidade de Aveiro, Portugal.

[2] Wikipédia. (2008) “Algoritmos de Busca”, http://pt.wikipedia.org/wiki/Algoritmo_de_busca,

Outubro.

[3] Wikipédia. (2008) “Algoritmos Binária”,

http://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria, Outubro.