Pesquisa-Busca Binária

Prévia do material em texto

Prof. Alexandre Sumoyama
Material: Prof. Matheus Franco
Estrutura de Dados II
Computação
A busca é o processo em que se determina
se um particular elemento x é membro de
uma determinado vetor V. Dizemos que a busca
tem sucesso se x∈V e que fracassa em caso
contrário.
Se não sabemos nada a respeito da
ordem em que os itens aparecem no
vetor, o melhor que podemos fazer é
uma busca linear. Entretanto, se os
itens aparecem ordenados, podemos
usar um método de busca muito mais
eficiente.
 Esse método é semelhante àquele que
usamos quando procuramos uma palavra num
dicionário: primeiro abrimos o dicionário
numa página aproximadamente no meio; se
tivermos sorte de encontrar a palavra nessa
página, ótimo; senão, verificamos se a palavra
procurada ocorre antes ou depois da página
em que abrimos e então continuamos, mais ou
menos do mesmo jeito, procurando a palavra
na primeira ou na segunda metade do
dicionário...
 Como a cada comparação realizada o espaço de 
busca reduz-se aproximadamente à metade, 
esse método é denominado busca binária.
x = am: nesse caso, o problema está resolvido; 
x < am: então x deverá ser procurado na primeira 
metade; 
x > am: então x deverá ser procurado na segunda 
metade.
 Caso a busca tenha que continuar, podemos
proceder exatamente da mesma maneira:
verificamos o item existente no meio da
metade escolhida e se ele ainda não for
aquele que procuramos, continuamos
procurando no meio do quarto escolhido,
depois no meio do oitavo e assim por diante
até que o item procurado seja encontrado ou
que não haja mais itens a examinar.
 Vamos simular o funcionamento do algoritmo de 
busca binária para determinar se o item x = 63 
pertence ao vetor V = 〈14, 27, 39, 46, 55, 63, 71, 80, 
92〉. Para indicar o intervalo em que será feita a busca, 
usaremos dois índices, i e f, e para indicar a posição 
central desse intervalo, o índice m.
 No primeiro passo o intervalo de busca
compreende todo o vetor, desde a posição 1 até a
posição 9, e o item central ocupa a posição 5. Como
x>V[5], a busca deve continuar na segunda metade
do vetor. Para indicar isso, atualizamos o índice i com
o valor 6 e repetimos o procedimento. No segundo
passo, o intervalo de busca foi reduzido aos itens que
ocupam as posições de 6 a 9 e o meio7 do vetor é a
posição 7. Agora x<V[7] e, portanto, a busca deve
continuar na primeira metade; então o índice f é
atualizado com o valor 6. No terceiro passo, resta um
único item no intervalo de busca e o meio do vetor é a
posição 6. Finalmente, temos x=V[6] e a busca
termina com sucesso
 Como em cada passo o intervalo de busca
reduz-se aproximadamente à metade, é
evidente que o processo de busca binária
sempre termina, mesmo que o item procurado
não conste do vetor. Nesse caso, o processo
somente termina quando não há mais itens a
examinar, ou seja, quando o intervalo de
busca fica vazio. Como o início e o final
do intervalo são representados pelos índices i
e f, o intervalo estará vazio se e somente se
tivermos i>f.
Durante a busca, o valor que indica o início do intervalo fica maior que
aquele que indica o seu final (veja 5º passo na tabela acima). Isso
significa que não há mais itens a considerar e que, portanto, o item
procurado não consta do vetor. Nesse caso, a busca deve terminar com
fracasso.
int buscabin(int x, int v[], int max) {
int i, f, m ;
i = 0; 
f = max-1; //limite indice do vetor
while (i<=f) { 
m = (i+f)/2; 
if (x==v[m]) 
return 1; 
else if (x<v[m]) 
f = m-1; 
else
i = m+1; 
} // fim while
return 0;
}
 Ao contrário da busca linear, a busca binária
somente funciona se o vetor estiver ordenado.
Isso pode ser uma desvantagem. Entretanto, à
medida em que o tamanho do vetor
aumenta, o número de comparações feitas
pelo algoritmo de busca binária tende a ser
muito menor que aquele feito pela busca
linear. Então, se o vetor é muito grande, e a
busca é uma operação muito requisitada,
esse aumento de eficiência pode
compensar o fato de termos que ordenar o
vetor antes de usar a pesquisa binária.
 Melhor caso T(n) = 1
 Pior caso T(n) = | log2n | +1
 Assim, em um caso médio, a quantidade de 
comparações cresce em função do log2n 
assim:
 O(log n)
 Quantos itens são examinados pelo algoritmo
de busca binária faz, no máximo, para
encontrar um item num vetor com 5000 itens?
 Seja n o número de itens no vetor, à medida em
que o algoritmo executa, o número de itens
vai reduzindo do seguinte modo:
5000 | 2500 | 1250 | 625 | 312 | 156 | 78 |
39 | 19 | 9 | 4 | 2 | 1 |
 Na sequência acima, cada redução implica numa
comparação. Logo, são realizadas no máximo
13 comparações.
1. Simule o funcionamento do algoritmo de busca 
binária para determinar se os itens 33, 50, 90 
constam do vetor L = 〈10, 16, 27, 31, 33, 37, 
41, 49, 53, 57, 68, 69, 72, 77, 84, 89, 95, 99〉. 
2. Dado um vetor de 131000 posições, quantos 
itens serão examinados no máximo para que 
ele encontre um determinado valor no vetor ou 
retorne que o valor não existe utilizando a 
busca binária?
3. E se o arranjo conter 55000 elementos?
4. Diferencie os métodos de busca sequencial e 
binária. Apresente duas complexidades 
comparando-as com um exemplo.