Pesquisa binária

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Pesquisa binária
classe Algoritmo de busca
estrutura de dados Array, Listas ligadas
complexidade caso médio {O}(\log n)
complexidade melhor caso {O}(1)
complexidade de espaços pior caso {O}(\log n)
otimo Sim
espaço {O}(1)
Algoritmos

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.

Análise de Complexidade[editar | editar código-fonte]

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).

Pseudo-Código[editar | editar código-fonte]

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
    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

Implementações[editar | editar código-fonte]

Código em Ruby[editar | editar código-fonte]

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[editar | editar código-fonte]

//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
}

Obs: A linguagem C fornece a função bsearch[1] na sua biblioteca padrão.

Java[editar | editar código-fonte]

public static int buscaBinaria( int[] tabela, int valor ) {
 
    boolean achou = false;
    int alto = tabela.length - 1;
    int baixo = 0;
    int meio = alto / 2;
 
    while (!achou && alto >= baixo) {
        if (valor == tabela[meio]) {
            achou = true;
        } else if (valor < tabela[meio]) {
            alto = meio -1;
        } else {
            baixo = meio + 1;
        }
        meio = (alto + baixo) / 2;
    }
    return ( (achou) ? meio : -1);
}

Código em python[editar | editar código-fonte]

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#[editar | editar código-fonte]

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[editar | editar código-fonte]

program Ordenamento;
    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[editar | editar código-fonte]

    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[editar | editar código-fonte]

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[editar | editar código-fonte]

    (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[editar | editar código-fonte]

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));

Código em VB.Net[editar | editar código-fonte]

  Private Function FindOrderBinarySearch(value As String, itemList As IList(Of Integer)) As Integer
 
        Dim midIndex As Integer
        Dim rigIndex As Integer = 0
        Dim lefIndex As Integer = itemList.Count - 1
 
        While rigIndex <= lefIndex
            midIndex = rigIndex + ((lefIndex - rigIndex) / 2)
            If itemList(midIndex) < value Then
                rigIndex = midIndex + 1
            ElseIf itemList(midIndex) > value Then
                lefIndex = midIndex - 1
            Else
                Return midIndex
            End If
        End While
 
        Return -1
    End Function

Referências

Ligações externas[editar | editar código-fonte]