Pesquisa binária
Origem: Wikipédia, a enciclopédia livre.
A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que requer acesso aleatório aos elementos do mesmo. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca (divisão e conquista) comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.
Índice |
[editar] Análise de Complexidade
A complexidade desse algoritmo é da ordem de Θ(log2 n), em que n é o tamanho do vetor de busca. Apresenta-se mais eficiente que a Busca linear cuja ordem é O(n).
[editar] Pseudo-Código
Um pseudo-código recursivo para esse algoritmo, dados V o vetor com elementos comparáveis, n seu tamanho e e o elemento que se deseja encontrar:
BUSCA-BINÁRIA (V[], início, fim, e)
i recebe o índice do meio entre início e fim
se (v[i] = e) entao
devolva o índice i # elemento e encontrado
senão (inicio = fim) entao
não encontrou o elemento procurado
senão
se (V[i] vem antes de e) então
faça a BUSCA-BINÁRIA(V, i+1, fim, e)
senão faça a BUSCA-BINÁRIA(V, inicio, i-1, e)
fimse
fimse
[editar] Implementações
[editar] Código em C
int PesquisaBinaria ( int array[], int chave , int N)
{
int inf = 0; //Limite inferior (o primeiro elemento do vetor em C é zero )
int sup = N-1; //Limite superior (termina em um número a menos 0 à 9 são 10 numeros )
int meio;
while (inf <= sup)
{
meio = (inf+sup)/2;
if (chave == array[meio])
return meio;
else if (chave < array[meio])
sup = meio-1;
else
inf = meio+1;
}
return -1; // não encontrado
}
Obs: A linguagem C fornece a função bsearch[1] na sua biblioteca padrão.
[editar] Código em Java
public static int buscaBinaria( int[] array, int valor )
{
int esq = 0;
int dir = array.length - 1;
int valorMeio;
while ( esq <= dir ) {
valorMeio = (esq + dir) / 2; // pode ocorrer estouro aritmético mas funciona (Y)
if ( array[valorMeio] < valor ) {
esq = valorMeio + 1;
} else if( array[valorMeio] > valor ) {
dir = valorMeio - 1;
} else {
return valorMeio;
}
}
return -1;
}
[editar] Código em python
def binsearch(seq, search):
right = len(seq)
left = 0
previous_center = -1
if search < seq[0]:
return -1
while 1:
center = (left + right) / 2
candidate = seq[center]
if search == candidate:
return center
if center == previous_center:
return - 2 - center
elif search < candidate:
right = center
else:
left = center
previous_center = center
[editar] Código em C#
private int PesquisaBinaria(int[] vetor, int inicio, int fim, int valorPesquisa)
{
int idxPivo = (inicio + fim) / 2;
if (valorPesquisa != vetor[idxPivo])
{
if (valorPesquisa < vetor[idxPivo])
{
idxPivo = PesquisaBinaria(vetor, inicio, idxPivo, valorPesquisa);
}
else
{
idxPivo = PesquisaBinaria(vetor, idxPivo, fim, valorPesquisa);
}
}
return idxPivo ; //retorna o indice da matriz em que contêm o
//o valor de entrada a ser pesquisado
}
[editar] Código em Pascal
function BuscaBinaria (Vetor: array of string; Chave: string; Dim: integer): integer;
var inicio, fim: integer; {Auxiliares que representam o inicio e o fim do vetor analisado}
meio: integer; {Meio do vetor}
begin
fim := Dim; {O valor do último índice do vetor}
inicio := 1; {O valor do primeiro índice do vetor}
repeat
meio := (inicio+fim) div 2;
if (Chave = vetor[meio]) then
BuscaBinaria := meio;
if (Chave < vetor[meio]) then
fim:=(meio-1);
if (Chave > vetor[meio]) then
inicio:=(meio+1);
until (Chave = Vetor[meio]) or (inicio > fim);
if (Chave = Vetor[meio]) then
BuscaBinaria := meio
else
BuscaBinaria := -1; {Retorna o valor encontrado, ou -1 se a chave nao foi encontrada.}
end;
[editar] Código Recursivo em Pascal
function BuscaBinariaRecursiva(var Vetor: array of string; L,H: integer; chave: string): integer;
var m:integer; {variavel auxiliar que indica o meio do vetor}
begin
ordena(Vetor,H); {Procedimento que ordena o vetor, tais como: bubble sort, quick sort, entre outros}
if L>H then {L= variavel que indica o começo do vetor, H= variavel que indica o fim do vetor}
BuscaBinariaRecursiva:=-1
else
begin
m:=(L+H) div 2;
if x<Vetor[M] then
BuscaBinariaRecursiva:=BuscaBinariaRecursiva(Vetor,L,M-1,x)
else
if x>Vetor[M] then
BuscaBinariaRecursiva:=BuscaBinariaRecursiva(Vetor,M+1,H,x)
else
BuscaBinariaRecursiva:=M;
end;
end;
[editar] Código em PHP
function buscaBinaria($valorPesquisa, array $vetor) { $n_elementos = count($vetor); $inicio = 0; $fim = $n_elementos -1; $meio = (int) (($fim - $inicio) / 2) + $inicio; while ($inicio <= $fim) { if ($vetor[$meio] < $valorPesquisa) { $inicio = $meio + 1; } elseif ($vetor[$meio] > $valorPesquisa) { $fim = $meio - 1; } else { return $meio; } $meio = (int) (($fim - $inicio) / 2) + $inicio; } return -1; } $a = array(1, 2, 3, 4, 5, 6); print "call buscaBinaria(4, [1, 2, 3, 4, 5, 6]); return: "; var_dump(buscaBinaria(4, $a)); print "call buscaBinaria(6, [1, 2, 3, 4, 5, 6]); return: "; var_dump(buscaBinaria(6, $a)); print "call buscaBinaria(1, [1, 2, 3, 4, 5, 6]); return: "; var_dump(buscaBinaria(1, $a)); print "call buscaBinaria(8, [1, 2, 3, 4, 5, 6]); return: "; var_dump(buscaBinaria(8, $a));
[editar] Fluxograma do algoritmo
Referências
[editar] Ligações externas
- Projeto de Algoritmos - Paulo Feofiloff -IME-USP
- NIST Dicionário de Algoritmos e Estrutura de Dados :binary search
- Tim Bray. On the Goodness of Binary Search. Pequeno ensaio das vantagens da busca binária e exemplo de código em Java.
- Explanação e código da busca binária em C++
- Google Research: Nearly All Binary Searches and Mergesorts are Broken
