C# Desenvolvimento Java Python Vídeo aulas

Busca Binária

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

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 

Danilo Filitto

Danilo Filitto

Mestre em Ciência da Computação pela UEM, Pós-Graduado em Redes de Computadores e Comunicação de Dados pela UEL, Bacharel em Ciência da Computação pela UNOESTE.

Adicione um comentário

Clique aqui para enviar um comentário

Área do assinante

Assinar Blog por Email

Digite seu endereço de email para assinar este blog e receber notificações de novas publicações por email.

Junte-se a 856 outros assinantes







Você gosta de jogar?