Busca Binária

A pesquisa ou busca binária é 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.

Busca Binária

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

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

Código em Java

public static int buscaBinaria(int[] array, int valor){
		int inicio = 0;
		int fim = array.length-1;
		
		while(inicio <= fim){
			int meio = (inicio+fim)/2;
			
			if(array[meio] == valor){
				return meio;
			}
			
			if(valor > array[meio]){
				inicio = meio+1;
			} else {
				fim = meio-1;
			}
		}
		return -1;
	}

Código em C#

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

Material escrito retirado do site da Wikipedia