Sucuuuu

PROGRAMAÇÃO DE COMPUTADORES I
Aula 22 Algoritmos de busca em memória principal: Busca Binária Prof. Marcus Vinícius de Ávila Couto

2

Busca Binária
• Um mecanismo mais eficiente de busca é análogo àquele

utilizado ao procurar uma palavra no dicionário;
• Faz-se uma estimativa da posição aproximada da palavra e

abre-se na página estimada. Se a palavra não foi encontrada nessa página, pelo menos sabe-se em que direção buscar, se mais adiante ou mais atrás no dicionário. O processo de estimar a nova página de busca repete-se até que a página com a palavra desejada seja encontrada;
• Esse mecanismo de busca só é possível porque as palavras

estão ordenadas no dicionário. Se o dicionário mantivesse as palavras sem nenhuma ordem, apenas a busca linear seria possível. Da mesma forma, a busca em uma lista de dados pode ser melhorada se seu conteúdo estiver ordenado.

3

Busca Binária
• O algoritmo de busca binária utiliza exatamente esse

princípio.
• No caso, a estimativa que é feita para a posição a ser buscada

é a posição mediana do restante da lista que falta para ser analisado;
• No início, o restante é a tabela toda; assim, a primeira posição

analisada é a entrada no meio da tabela. Se não for a entrada buscada, analisa-se a metade que resta, ou a inferior (se a chave encontrada tem valor maior que a que se busca) ou a superior (em caso contrário). O procedimento assim se repete, até que se encontre a chave buscada ou que a busca se esgote sem encontrar essa chave.

4

Busca Binária int Função buscaBinaria(int elemen, int V[], int N) int meio, inicio, fim; inicio = 1; fim = N; // Enquanto a parte restante for maior que zero Enquanto (inicio <= fim) faça meio = (inicio + fim) /2; Se (elemen < vet[meio]) Então fim = meio -1; // ajusta posição final Senão Se (elemen > vet[meio]) Então inicio = meio + 1; // ajusta posição inicial Senão retorna meio; Fim-Se; Fim-Enquanto; // Não encontrou retornar -1; Fim-Função;

5

Exercícios
1.
a)

Responda as seguintes