quarta-feira, 8 de maio de 2013

[Programação em C] Busca binária

Olá pessoal, nesse post vamos falar um pouco sobre a busca binária que é um algoritmo mais eficiente do que a busca linear.

A primeira coisa que devemos ter em mente é que, na busca binária, os elementos do vetor tem que está ordenados. O que iremos fazer é testar o elemento que queremos buscar com o valor do elemento que encontra-se no meio do vetor.

Vamos imaginar que temos um vetor ordenado da seguinte forma:


vetor = {1, 6, 8, 10, 12, 18}

Pois bem, no nosso vetor temos seis elementos. Vamos supor que queremos buscar o elemento 12. Eu disse anteriormente que a ideia é testar o elemento que queremos buscar com o valor do elemento que está no meio do vetor.

Como saber a posição que identifica o meio do vetor? É um cálculo simples, a posição inicial começa do 0, pois o vetor começa da posição 0. Já a posição final é o número de elementos do vetor menos 1. 

inicio = 0
fim = num - 1
"num" é a quantidade de elementos do vetor

Para o nosso exemplo:
num = 6
inicio = 0
fim = 6 - 1 = 5

Para obter o meio:
meio = (inicio + fim) / 2

Para o nosso exemplo:
meio = (0 + 5) / 2
meio = 2

A posição do meio é 2. Qual elemento no nosso exemplo está na posição 2? Lembrando que o vetor começa da posição 0...

vetor = {1, 6, 8, 10, 12, 18}

O elemento que está no meio (posição 2) do vetor é o 8. O elemento que queremos buscar é o 12. Se o elemento que buscamos é maior que o elemento que está no meio do vetor, então podemos concluir que o elemento que buscamos está na segunda parte do vetor.

12 (elemento que buscamos) é maior que 8 (elemento que está no meio do vetor). Então o elemento que buscamos está na segunda parte do vetor. Essa segunda parte é:

{10, 12, 18}

O que fazer quando sabemos que o elemento está na segunda parte do vetor? É só ajustar a posição inicial. Nesse caso não precisa ajustar a posição final, pois a posição final continua sendo a mesma. Mas por que ajustar a posição inicial? Você tem que ajustar essa posição para poder obter corretamente a posição do meio do vetor.

Ajustando a posição inicial:
inicio = meio + 1
inicio = 2 + 1 = 3
Lembre-se que a nossa variável "meio" era 2!

Calcula-se novamente o meio:
meio = (inicio + fim) / 2
meio = (3 + 5) / 2 = 8 / 2 = 4

Ok, agora vamos comparar o elemento que buscamos (número 12) com o elemento que está no meio do vetor, ou seja, na posição 4 que é o número 12. O elemento que buscamos não é menor nem é maior do que o elemento do meio. Ele é igual, então é só retornar a posição que se encontra esse elemento que é justamente o que representa a variável "meio". Terminou a busca.

Tudo bem, vimos a situação quando o elemento está na segunda parte e quando ele é igual. Mas e quando o elemento está na primeira parte? Novamente voltamos ao exemplo:

vetor = {1, 6, 8, 10, 12, 18}

Iremos buscar o elemento 6. Já calculamos na busca anterior o meio desse vetor que é 2. O elemento do meio (posição 2) é o número 8.

O elemento que buscamos (número 6) é menor que o elemento do meio (número 8), então podemos concluir que o elemento que buscamos está na primeira parte do vetor.

Se o elemento que buscamos está na primeira parte do vetor:

{1, 6}

Então não iremos precisar ajustar a posição inicial, só precisaremos ajustar a posição final. Veja:

fim = meio - 1 = 2 - 1  = 1

Calculando o meio:
meio = (inicio + fim) / 2
meio = (0 + 1) / 2 = 0

O meio agora é 0, o elemento que está na posição 0 é o número 1. O elemento que buscamos (número 6) é maior que o elemento do meio (número 1). Então podemos concluir que o elemento está na segunda parte do vetor. Se está na segunda parte, já sabemos que precisamos ajustar a posição inicial:

inicio = meio + 1 = 0 + 1 = 1

Calculando o meio:
meio = (inicio + fim) / 2
meio = (1 + 1) / 2 = 1

Agora o elemento que está no meio do vetor é o elemento da posição 1. Esse elemento é o número 6. O elemento que buscamos também é o número 6, ou seja, são iguais. Então é só retornar a posição do elemento que é justamente o valor da variável "meio".

Então podemos ver que o algoritmo consiste em subdividir até encontrar o elemento. Você vai aplicando o processo enquanto a parte restante for maior que zero, ou seja, enquanto a variável "inicio" for menor ou igual a variável "fim".

Dentro do loop, você calcula o meio, depois verifica se o elemento que buscamos é menor do que o elemento que está na posição do meio, se cair nessa condição então ajusta a posição final. Se o elemento que buscamos for maior que o elemento que está na posição do meio, então ajusta a posição inicial. Se não cair em nenhum desses dois casos, então é porque o elemento foi encontrado e aí é só retornar a posição do elemento que é a variável "meio".

Se sair do loop, então é porque o elemento não foi encontrado.

A ordem do algoritmo de busca binária é O(log n).

Você consegue montar um programa para fazer a busca binária com essa explicação? Tente fazer antes de clicar nos links abaixo.

Clique aqui para ver a implementação

Clique aqui para fazer o download do código


Nenhum comentário: