5.4. A Busca Binária¶

É possível obter uma grande vantagem do fato de uma lista estar ordenada se formos espertos o bastante com as nossas comparações. Na busca sequencial, quando iniciamos a comparação a partir do primeiro item, há no máximo mais $n-1$ elementos a serem buscados se o primeiro item não era o que estávamos procurando. Em vez de procurar o item sequencialmente, uma busca binária irá começar examinando o item do meio. Se esse elemento é o que estamos buscando, a procura terminou. Se não for o item correto, podemos utilizar o fato da lista estar ordenada para eliminar metade dela. Se o item que estamos procurando for maior que o elemento do meio, sabemos que a metade inferior (contando com o item do meio) não precisa mais ser levada em consideração. O item, se estiver na lista, necessariamente está na metade superior.

Podemos então repetir o processo com a parte superior. Começamos pelo item do meio e o comparamos com o que estamos buscando. Novamente, ou o item do meio é igual ao que buscamos, ou divimos a lista no meio, eliminando então outra parte considerável do nosso espaço de busca. A Figura 3 mostra como esse algoritmo consegue encontrar rapidamente o valor 54. A função completa é exibida em CodeLens 3.

Figura 3: Busca Binária em Uma Lista Ordenada de Inteiros¶

Python 3.3

	1	def binarySearch(alist, item):
	2	first = 0
	3	last = len(alist)-1
	4	found = False
	5
	6	while first<=last and not found:
	7	midpoint = (first + last)//2
	8	if alist[midpoint] == item:
	9	found = True
	10	else:
	11	if item < alist[midpoint]:
	12	last = midpoint-1
	13	else:
	14	first = midpoint+1
	15
	16	return found
	17
	18	testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
	19	print(binarySearch(testlist, 3))
	20	print(binarySearch(testlist, 13))

Step 1 of 42

line that has just executed

next line to execute

Visualized using Online Python Tutor by Philip Guo

Frames

Objects

Busca Binária em uma Lista Ordenada (search3)

Antes de irmos para a análise, note que esse algoritmo é um ótimo exemplo da estratégia de dividir para conquistar, isto é, nós dividimos o problema em partes menores, resolvemos as menores partes de algum modo e então remontamos tudo para chegar ao resultado. Quando nós realizamos uma busca binária de uma lista, primeiro checamos o item do meio. Se o item que estamos procurando é menor que o item intermediário, nós simplesmente fazer uma busca binária na metade esquerda da lista original. Do mesmo modo, se o item for maior, nós realizamos uma binária na metade direita. De qualquer forma, trata-se de uma chamada recursiva da função de busca binária passando uma lista menor como parâmetro. CodeLens 4 mostra essa versão recursiva.

Python 3.3

	1	def binarySearch(alist, item):
	2	if len(alist) == 0:
	3	return False
	4	else:
	5	midpoint = len(alist)//2
	6	if alist[midpoint]==item:
	7	return True
	8	else:
	9	if item<alist[midpoint]:
	10	return binarySearch(alist[:midpoint],item)
	11	else:
	12	return binarySearch(alist[midpoint+1:],item)
	13
	14	testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
	15	print(binarySearch(testlist, 3))
	16	print(binarySearch(testlist, 13))

Step 1 of 35

line that has just executed

next line to execute

Visualized using Online Python Tutor by Philip Guo

Frames

Objects

Uma Busca Binária--Versão Recursiva (search4)

5.4.1. Análise da Busca Binária¶

Para analisar o algoritmo de busca binária, precisamos ter em mente que cada comparação elimina cerca de metade dos itens restantes a serem considerados. Qual é o número máximo de comparações que esse algoritmo irá requerer para checar a lista inteira? Se começarmos com n itens, em torno de $\frac{n}{2}$ itens sobrarão após a primeira comparação. Depois da segunda comparação, haverá cerca de $\frac{n}{4}$ , depois $\frac{n}{8}$ , $\frac{n}{16}$ e assim por diante. Mas quantas vezes podemos dividir essa lista? A Tabela 3 nos ajuda a responder essa pergunta.

**Tabela 3: Análise da Busca Binária**¶
Comparações	Número aproximado de itens restantes
1	$\frac {n}{2}$
2	$\frac {n}{4}$
3	$\frac {n}{8}$
…
i	$\frac {n}{2^i}$

Quando nós quebramos a lista um número suficiente de vezes, acabamos ficando com uma lista composta por um único item. Logo, ou esse item é aquele que estamos buscando ou não é. De qualquer forma, o processo termina. O número necessário de comparações para chegar a esse ponto é i, onde $\frac {n}{2^i} = 1$ . Isolando i, ficamos com $i=\log n$ . Assim, o número máximo de comparações é o logaritmo do número de itens na lista. Portanto, a busca binária é $O(\log n)$ .

Uma questão adicional de análise ainda precisa ser tratada. Na solução recursiva mostrada acima, a chamada recursiva

binarySearch(alist[:midpoint],item)

usa o operador de fatiamento para criar a metade esquerda da lista que é passada para a próxima chamada (e, da mesma maneira, para a metade direita). A análise que fizemos acima pressupõe que o operador de fatiamento tem tempo constante. Contudo, nós sabemos que na verdade o operador de fatiamento em Python é O(k). Isso significa que a busca binária usando esse operador não irá ter um desempenho estritamente logarítmico. Felizmente isso pode ser remediado passando a lista junto com os índices de começo e fim. Os índices podem ser calculados como fizemos em Listing 3 <lst_binarysearchpy>`. Deixamos essa implementação como um exercício.

Embora uma busca binária seja geralmente melhor que uma sequencial, é importante notar que para valores pequenos de n, o custo adicional de ordenar a lista provavelmente não vale a pena. Na verdade, sempre deveríamos considerar o custo-benefício do trabalho adicional de ordenação para obter benefícios na busca. Se nós podemos ordenar uma vez e então fazer inúmeras buscas, o custo da ordenação não é tão significativo. Entretanto, para listas muito grandes, a ordenação, mesmo que feita uma única vez, pode ser tão cara que simplesmente fazer uma busca sequencial desde o começo pode se mostrar uma escolha melhor.

Auto-avaliação

Q-1: Suponha que você tenha a lista ordenada [3, 5, 6, 8, 11, 12, 14, 15, 17, 18] e que você esteja usando o algoritmo recursivo da busca binária. Qual grupo de números mostra corretamente a sequência de comparações usadas para encontrar a chave 8?

Q-2: Suponha que você tenha a lista ordenada [3, 5, 6, 8, 11, 12, 14, 15, 17, 18] e que você esteja usando o algoritmo recursivo da busca binária. Qual grupo de números mostra corretamente a sequência de comparações usadas para encontrar a chave 16?

Next Section - 5.5. Hashing

5.4. A Busca Binária¶

5.4.1. Análise da Busca Binária¶

Scratch ActiveCode