Pesquisa binária – Wikipédia a enciclopédia livre

Prévia do material em texto

Pesquisa binária
classe Algoritmo de busca
estrutura de dados Array, Listas ligadas
complexidade caso
médio
complexidade
melhor caso
complexidade de
espaços pior caso
otimo Sim
espaço
Algoritmos
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 segue o paradigma de divisão e
conquista. Ela parte do pressuposto de que o vetor está
ordenado e realiza sucessivas divisões do espaço de
busca 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
1 Análise de Complexidade
2 Pseudo-Código
3 Implementações
3.1 Código em Ruby
3.2 Código em C
3.3 Java
3.4 Código em python
3.5 Código em C#
3.6 Código em Pascal
3.7 Código Recursivo em Pascal
3.8 Código em Lua
3.9 Código em Scheme
3.10 Código em PHP
4 Referências
5 Ligações externas
Análise de Complexidade
A complexidade desse algoritmo é da ordem de Θ(log n), em que n é o tamanho do vetor de busca.
Apresenta-se mais eficiente que a Busca linear cuja ordem é O(n).
Pseudo-Código
Um pseudo-código recursivo para esse algoritmo, dados V o vetor com elementos comparáveis, n seu tamanho
2
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
 fimse
 se (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
allan alvez bonifacio
Implementações
Código em Ruby
def search(vector, lower, upper, element)
 return -1 if lower > upper
 mid = (lower+upper)/2
 if (vector[mid] == element)
 element
 elsif (element < vector[mid])
 search(vector, lower, mid-1, element)
 else
 search(vector, mid+1, upper, element)
 end
end
 
def binary_search(vector,element)
 search(vector, 0, vector.size-1, element)
end
Código em C
//em C para se passar um vetor como parâmetro para uma função, tem que se passar o ponteiro do vetor
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-inf)/2;
 if (chave == array[meio])
 return meio;
 else if (chave < array[meio])
 sup = meio-1;
 else
 inf = meio+1;
 }
 return -1; // não encontrado
}
[1]
Obs: A linguagem C fornece a função bsearch na sua biblioteca padrão.
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 - esq) / 2);
 if ( array[valorMeio] < valor ) {
 esq = valorMeio + 1;
 } else if( array[valorMeio] > valor ) {
 dir = valorMeio - 1;
 } else {
 return valorMeio;
 }
 }
 return -1;
}
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
Código em C#
[1]
static int pesquisaBinaria(int[] vetor, int chave)
 {
 //Ordena o vetor.
 Array.Sort(vetor);
 
 int meio;
 int Min = 0;
 int Max = vetor.Length - 1;
 
 do
 {
 meio = (int)(Min + Max) / 2;
 if (vetor[meio] == chave)
 {
 //Retorna a posição do número na seqüencia.
 return meio;
 }
 else if (chave > vetor[meio])
 Min = meio + 1;
 else
 Max = meio - 1;
 }
 while (Min <= Max);
 
 //Caso o retorno for -1, então o número não existe na seqüencia.
 return -1;
 }
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}
 BuscaBinaria := -1; {Retorna o valor -1 se a chave nao for encontrada.}
 repeat
 meio := (inicio+fim) div 2;
 if (Chave = vetor[meio]) then
 begin
 BuscaBinaria := meio;
 inicio:=fim+1; {Interrompo o repeat quando a chave for encontrada sem ter que testar lá no until. Bonito não?!}
 end;
 if (Chave < vetor[meio]) then 
 fim:=(meio-1); 
 if (Chave > vetor[meio]) then
 inicio:=(meio+1);
 until (inicio > fim);
 end;
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;
Código em Lua
function buscaBinaria(v, x)
 ini = 1
 fim = #v
 while(ini<=fim)
 do
 pivo= math.floor((fim+ini)/2)
 if(x > v[pivo])
 then
 ini = pivo+1
 end
 
 if(x < v[pivo])
 then
 fim = pivo-1
 end
 
 if (x==v[pivo])
 then
 return pivo
 end
 end
 return -1
end
Código em Scheme
 (define vetor (vector 1 2 4 6 8 9 10 23 45 ))
 (define (buscab vetor numero inicio fim)
 (letrec ([ndivi (floor (/ (+ fim inicio) 2))] [n-medio (vector-ref vetor ndivi)])
 (cond
 [(> inicio fim) false]
 [(= numero n-medio) ndivi]
 [(< numero n-medio) (buscab vetor numero inicio (- ndivi 1))]
 [else (> numero n-medio) (buscab vetor numero (+ ndivi 1) fim)])))
 (buscab vetor 23 0 9)
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));
Referências
1. ↑ bsearch(3) - binary search of a sorted array (http://linux.die.net/man/3/bsearch)
Ligações externas
Tecnologia da Informação - Goiânia - GO (http://www.go.senac.br/faculdade)
Projeto de Algoritmos - Paulo Feofiloff -IME-USP
(http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.html)
NIST Dicionário de Algoritmos e Estrutura de Dados :binary search
(http://www.nist.gov/dads/HTML/binarySearch.html)
Tim Bray. On the Goodness of Binary Search
(http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary) . 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++ (http://www.datastructures.info/what-is-a-binary-seach-
algorithm-and-how-does-it-work/)
Google Research: Nearly All Binary Searches and Mergesorts are Broken
(http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html)
Obtida de "http://pt.wikipedia.org/w/index.php?title=Pesquisa_binária&oldid=33162759"
Categoria: Algoritmos de busca
Esta página foi modificada pela última vez à(s) 17h39min de 3 de dezembro de 2012.
Este texto é disponibilizado nos termos da licença Atribuição-Partilha nos Mesmos Termos 3.0 não
Adaptada (CC BY-SA 3.0); pode estar sujeito a condições adicionais. Consulte as condições de uso
para mais detalhes.