Busca Linear e Busca Binária

Prévia do material em texto

Universidade Presbiteriana Mackenzie 
Métodos de Pesquisa ou Busca 
Busca Linear e Busca Binária 
Profa. Ana Cristina dos Santos 
Faculdade de Computação e Informática 
Estrutura de Dados 2 1 
Especificação do Problema 
• A tarefa de pesquisar ou buscar está entre as 
tarefas mais frequentemente encontradas no dia-
a-dia. 
 
• Veremos algoritmos para o problema de 
recuperar informação a partir de uma massa 
grande de informação previamente armazenada 
 
2 Busca Linear e Busca Binária 
Representação das informações 
• A informação geralmente é dividida em registros, 
onde cada registro possui uma chave para ser usada 
na pesquisa 
• Chave: componente de uma estrutura, ou de um 
registro de banco de dados, segundo o qual se 
realiza a busca 
• Objetivo: encontrar uma ou mais ocorrências de u 
registros com chaves iguais à chave de pesquisa, 
ocorrendo sucesso ou insucesso na pesquisa. 
• Conjunto de registros: chamado de tabela ou 
arquivos. 
 
3 Busca Linear e Busca Binária 
Representação das informações 
• Tabelas: termo associado à entidades de vida curta, 
criadas na memória interna, durante a execução de um 
programa; 
• Arquivos: entidades de vida mais longa, armazenadas na 
memória externa. 
• O conjunto de elementos onde será efetuada a 
pesquisa, muitas vezes será representado através de um 
vetor ou lista, onde cada item apresenta uma estrutura 
de registro, contendo um campo que atua como chave 
para a pesquisa 
 
 
4 Busca Linear e Busca Binária 
Especificação do Problema 
 
• Dado um conjunto com N elementos do mesmo 
tipo de dado armazenados em um vetor V, 
retornar em qual posição (índice do vetor) 
encontra-se o elemento de valor X, ou -1 caso o 
elemento não se encontre no vetor. 
5 Busca Linear e Busca Binária 
6 
Visualização do Problema 
 
 
3015201012
Vetor V = { 12, 10, 20, 15, 30 } N = 5 X = 15 
Índice no vetor 
Vetor V 
Qual a posição do Elemento X em V ? 
43210
Busca Linear e Busca Binária 
Métodos de Busca 
• Existe uma variedade de métodos de 
pesquisa. 
• A escolha do método mais adequado a uma 
determinada aplicação depende: 
– da quantidade de dados envolvidos e 
– do arquivo estar sujeito a inserções e retiradas 
constantes 
7 Busca Linear e Busca Binária 
Métodos de Busca 
• Há dois métodos de busca classicamente 
utilizados: 
 
– Busca Linear 
– Busca Binária 
8 Busca Linear e Busca Binária 
Busca Linear 
• Estratégia: 
 
– Percorrer o vetor da posição inicial até a final, 
comparando cada elemento com o elemento de busca 
– Quando encontrar o elemento, devolver a posição 
– Caso contrário, devolver que o elemento não foi 
encontrado 
9 Busca Linear e Busca Binária 
Busca Linear 
 
 
3015201012
Vetor V = { 12, 10, 20, 15, 30 } N = 5 X = 15 
43210
i 
Índice 
no vetor 
Vetor V 
Variável para controlar a posição do 
elemento do vetor que deve ser 
comparado com X 
10 Busca Linear e Busca Binária 
Método Busca Linear 
// Pesquisar de 0 a n – 1 
public int buscaLinear (int [] v, int n, int x){ 
 for (int i = 0; i < n; i++){ 
 if (v[i] == x) 
 return i; 
 } 
 return -1; //Não encontrou! 
} 
11 Busca Linear e Busca Binária 
Método Busca Linear - Sobrecarga 
public int buscaLinear (int [] v, int x) 
{ 
 return buscaLinear (v, v.length, x); 
} 
12 Busca Linear e Busca Binária 
Desempenho da Busca Linear 
Melhor Caso: A chave de pesquisa ou o elemento 
procurado é o primeiro. O algoritmo faz apenas uma 
comparação, logo complexidade constante: O (1) 
 
Pior Caso: O elemento procurado não está no vetor. O 
número de comparações é proporcional ao tamanho do 
vetor. Logo, O (n) 
13 Busca Linear e Busca Binária 
Busca Binária 
• Estratégia: 
– Ordenar o Vetor 
– Encontrar a posição do meio 
– Comparar se o elemento do meio é menor, maior ou igual 
ao elemento de busca. 
• Se elemento foi encontrado, é o fim da busca 
• Senão, do resultado desta comparação, definir se a 
busca continuará: 
– Na primeira metade do vetor (inferior) 
– Na segunda metade do vetor (superior) 
– Repetir o processo até que todos os elementos tenham 
sido analisados 
14 Busca Linear e Busca Binária 
Busca Binária 
 
 
5040302010 10090807060
Vetor V = { 10,20,30,40,50,60,70,80,90,100 } 
N = 10 X = 70 
Índice 
no vetor 
Vetor V 
43210 98765
ini fim meio 
Posição 
inicial do 
vetor Variável para 
controlar a 
posição meio 
do vetor 
X > V[meio], então 
a busca continua na 
metade superior 
do vetor 
Variável para 
controlar a 
posição final 
do vetor 
 15 Busca Linear e Busca Binária 
Busca Binária 
 
 
5040302010 10090807060
X = 70 
43210 98765
ini fim meio 
ini fim meio 
ini fim 
meio 
ini 
fim 
meio 
Índice 
Vetor V 
A posição do meio é 
calculada pela seguinte 
expressão: 
 
Meio ← (ini+fim)/2 
16 Busca Linear e Busca Binária 
Método de Busca Binária Iterativo 
public int buscaBinaria (int [] v, int n, int x){ 
 int ini= 0, fim = n-1, meio; 
 
 while (ini <= fim){ 
 meio = (ini + fim) / 2; 
 if (v[meio]==x) // Encontrou! 
 return meio; 
 else if (x > v[meio] ) // Busca na segunda metade 
 ini = meio + 1; 
 else // Busca na primeira metade 
 fim = meio - 1; 
 } 
 return -1; //Não encontrou! 
} 
17 Busca Linear e Busca Binária 
Método de Busca Binária Iterativo - 
Sobrecarga 
public int binSearch(int [] v, int x) 
{ 
 return binSearch(v,0,v.length-1,x); 
} 
18 Busca Linear e Busca Binária 
Busca Binária Recursiva 
public int buscaBinaria(int [] v, int ini, int fim, int x){ 
 if (ini > fim) 
 return -1; //Não encontrou! 
 int meio = (ini + fim) / 2; 
 if (x == v[meio]) // Encontrou! 
 return meio; 
 else if (x > v[meio]) // Busca do lado direito 
 return buscaBinaria(v, meio+1, fim, x); 
 else // Busca do lado esquerdo 
 return buscaBinaria(v, ini, meio-1, x); 
} 
19 Busca Linear e Busca Binária 
A Classe Busca 
//Classe Busca 
public class Busca { 
// Vários métodos 
public int buscaLinear ( ... ) { ... } 
public int buscaBinaria ( ... ) { ... } 
} 
20 Busca Linear e Busca Binária 
Comparação de Desempenho 
• Qual método de busca é melhor, para um 
vetor de tamanho N? 
– Podemos verificar que o custo da Busca Linear é 
proporcional ao tamanho do vetor, ou seja a N 
– Já o custo da busca binária é proporcional ao 
logaritmo na base 2 de N: log2 N 
21 Busca Linear e Busca Binária 
Busca Binária: Pior Caso 
Ocorre quando o elemento procurado não pertence a lista 
Vamos mostrar que o desempenho será: Ο(log n) 
 
Para tanto, vamos considerar a instrução mais importante 
do algoritmo como sendo as comparações 
 x < v[meio] e x > v[meio]. 
O valor procurado é comparado 2 vezes com o registro 
apontado pelo meio do vetor. 
Em seguida o processo é repetido com uma das sublistas. 
 
22 Busca Linear e Busca Binária 
Busca Binária: Pior Caso 
Portanto, até aqui sabemos que o número de comparações 
é: 
T(n) = 2 + T(p), em que p = tamanho da sublista 
 
[sublista da esquerda]  [sublista da direita] 
 Meio 
Mas p = n/2, portanto, T(n) = 2 + T(n/2) 
 
Suponha n = 1, teremos T(n) = 2 
Para n = 5, teremos: T(5) = 2 + T(2) = 2 + { 2 + T(1) } = 6 
 
23 Busca Linear e Busca Binária 
Busca Binária: Pior Caso 
• Para calcular T(n), para qualquer n, é preciso encontrar 
uma fórmula direta, T(n), que não sejaRecorrente como o 
exemplo anterior. 
• Podemos encontrar a função que desejamos por 
observação: 
 
24 Busca Linear e Busca Binária 
Busca Binária: Pior Caso 
n T(n) 
 1 2 + 0 = 2 
 2 2 + T(1) = 4 
 3 2 + T(1) = 4 
 4 2 + T(2) = 2 + 2 + T(1) = 6 
 5 2 + T(2) = 2 + 2 + T(1) = 6 
 6 2 + T(2) = 2 + 2 + T(1) = 6 
 7 2 + T(2) = 2 + 2 + T(1) = 6 
 8 2 + T(4) = 2 + 2 + T(2) = 2 +2 + 2 + T(1) = 8 
.... 
 16 2 + T(8) = 10 
.... 
 32 2 + T(16) = 12 
25 Busca Linear e Busca Binária 
Busca Binária: Pior Caso 
• Os valores da função de complexidade muda quando n= 1, 
2, 4, 8 , 16...., ou seja, os valores “especiais” são potências 
de 2: 20, 21, 22, 24... 
 
 N T(n) 
20 = 1 2 + 0 = 2 
21 = 2 2 + 2 = 4 
22 = 4 2 + 4 = 6 
23 = 8 2 + 6 = 8 
24 = 16 2 + 8 = 10 
dobro do expoente 
26 Busca Linear e Busca Binária 
Busca Binária: Pior Caso 
• Portanto T(n) = 2 + 2k, onde k é o expoente da potência 
de dois desses valores. 
• Mas k deve ser expresso em função de n. 
• Para tanto, 
 2k = n 
 log2 2
k = log2 n 
 k. log22 = log2n 
 k = log2n 
 
 
 
 
 
 
27 Busca Linear e Busca Binária 
Busca Binária: Pior Caso 
Então podemos dizer que k é k = log2n 
 Logo, 
 T(n) = 2 + 2 log2n, 
• desprezando as constantes aditivas e multiplicativas 
temos: 
 T(n) = 2 + 2 log2n 
 
 T(n) = O(log n) 
 
 
28 Busca Linear e Busca Binária 
Exercício 
Fazer a pilha de execução para a Busca Binária 
com a entrada: ini=0, fim=5, x=22 e 
v={5,7,10,15,20,22} . 
 
 
29 Busca Linear e Busca Binária 
Exercício 
buscaBin (V={5,7,10,15,20,22} , ini = 0 , fim = 5, x = 22 ) 
 meio=2 
meio = 
buscaBin(V={15,20,22} , ini = 3, fim = 5, x = 22 ) 
 meio=4 
meio = 
buscaBin(V={22} , ini = 5 , fim = 5, x = 22 ) 
 meio=5 
 retorna 5 
retorna 5 
retorna 5 
30 Busca Linear e Busca Binária 
Obrigada 
 
 
 
Ana Cristina dos Santos 
anacristina.santos@mackenzie.br 
31 Busca Linear e Busca Binária