Pesquisa binriaOrigem: Wikipdia, a enciclopdia livre.
A pesquisa ou busca binria (em ingls binary search algorithm ou
binary chop) um algoritmo de busca em vetores que requer acesso
aleatrio aos elementos do mesmo. Ela parte do pressuposto de que o
vetor est ordenado e realiza sucessivas divises do espao de busca
(diviso 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 contrrio, se o elemento do
meio vier antes do elemento buscado, ento 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
[esconder] 1 Anlise de Complexidade 2 Pseudo-Cdigo 3 Implementaes
3.1 Cdigo em Ruby 3.2 Cdigo em C 3.3 Java 3.4 Cdigo em python 3.5
Cdigo em C# 3.6 Cdigo em Pascal 3.7 Cdigo Recursivo em Pascal 3.8
Cdigo em Lua 3.9 Cdigo em Scheme 3.10 Cdigo em PHP 4 Referncias 5
Ligaes externas
[editar]
Anlise de ComplexidadeA 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-Cdigo
Um pseudo-cdigo recursivo para esse algoritmo, dados V o vetor
com elementos comparveis, n seu tamanho e e o elemento que se
deseja encontrar: BUSCA-BINRIA (V[], incio, fim, e) i recebe o
ndice do meio entre incio e fim se (v[i] = e) entao devolva o ndice
i # elemento e encontrado fimse se (inicio = fim) entao no
encontrou o elemento procurado seno se (V[i] vem antes de e) ento
faa a BUSCA-BINRIA(V, i+1, fim, e) seno faa a BUSCA-BINRIA(V,
inicio, i-1, e) fimse fimse [editar]
Implementaes[editar]
Cdigo em Rubydef 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 [editar]
Cdigo em C//em C para se passar um vetor como parmetro para uma
funo, 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 nmero a
menos 0 9 so 10 numeros ) int meio; while (inf vetor[meio]) Min
= meio + 1; else Max = meio - 1; } while (Min vetor[meio]) then
inicio:=(meio+1); until (inicio > fim); end; [editar]
Cdigo Recursivo em Pascalfunction 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 comeo do vetor, H= variavel que indica o fim do vetor}
BuscaBinariaRecursiva:=-1 else begin m:=(L+H) div 2; if xVetor[M]
then BuscaBinariaRecursiva:=BuscaBinariaRecursiva(Vetor,M+ 1,H,x)
else BuscaBinariaRecursiva:=M; end;
end; [editar]
Cdigo em Luafunction buscaBinaria(v, x) ini = 1 fim = #v
while(ini 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 [editar]
Cdigo 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) [editar]
Cdigo em PHPfunction buscaBinaria($valorPesquisa, array $vetor)
{
$n_elementos = count($vetor); $inicio = 0; $fim = $n_elementos
-1; $meio = (int) (($fim - $inicio) / 2) + $inicio; while ($inicio
$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,
var_dump(buscaBinaria(4, $a)); print "call buscaBinaria(6, [1,
var_dump(buscaBinaria(6, $a)); print "call buscaBinaria(1, [1,
var_dump(buscaBinaria(1, $a)); print "call buscaBinaria(8, [1,
var_dump(buscaBinaria(8, $a)); 2, 3, 4, 5, 6]); return: "; 2, 3, 4,
5, 6]); return: "; 2, 3, 4, 5, 6]); return: "; 2, 3, 4, 5, 6]);
return: ";
