Busca Binária

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. A busca binária parte do pré-suposto que o algoritmo está ordenado, então pode-se fazer a busca.

---

Algoritmo

Busca_Binaria(vetor, itemBuscado, tamanhoVetor)

   inicio <- 0
   fim <- tamanho -1
   meio <- 0
 
   Enquanto inicio <= fim faça
   
    meio <- (inicio + fim)/2
    
    Se vetor[meio] for igual a itemBuscado
          retorna meio
     
    Se itemBuscado for maior do que vetor[meio]
          inicio <- meio + 1
    
     Senão
          fim <- meio - 1

______________________________________

Olhando para o Vetor!

Vetor[ ] = {1, 2, 3, 4, 5, 6, 7, 8, 9}

Temos os índices de 0 à 8, inicial e final respectivamente.

O cálculo para saber o meio é (inicio + fim) / 2, que nos retornará o valor 4, ou seja, o índice 4 onde encontra-se o valor 5, aí está definido nosso meio inicial tendo como base todo o vetor. Perceba que agora temos do lado esquerdo do vetor os números {1, 2, 3, 4} e do lado direito, {6, 7, 8, 9}. Suponhamos que queremos buscar o número 8, Qual o cálculo que será feito?

---

Encontrando o Número 8

Enquanto inicio <= fim faça

    meio <- (inicio + fim)/2        
    Se vetor[meio] for igual a itemBuscado
          retorna meio

Claramente o item buscado é maior do que o número que encontra-se no índice do meio, então passa para a próxima condição:

Se itemBuscado for maior do que vetor[meio] inicio <- meio + 1

Agora vemos que esta condição é satisfeita, nosso início agora passa a ser meio + 1, ou seja, o índice 5, onde se encontra o valor 6. O lado esquerdo não mais será usado para a busca, nosso início passa a ser como citado acima. A última condição não é satisfeita, pois sabemos que o número é maior do que o vetor[meio].

---

Código em C

int buscaBinaria(int vetor[], int item, int tamanho){

int inicio = 1;
int fim = tamanho - 1;
int meio;

while (inicio <= fim){
	
	meio = (inicio + fim) / 2;

	if (vetor[meio] == item ){

		return meio;
		
	}
	if (item > vetor[meio]){

		inicio = meio + 1;
		
	}
	else{

		fim = meio - 1;

	}
}

return -1;

}

_______________________________________________

Código em Python

def buscaBinaria(vetor, item, tamanho):

meio = 0
inicio = 0
fim = tamanho - 1

while inicio <= fim:
	
	meio = (inicio + fim)/2

	if (item == vetor[meio]):			
		
		return meio
		

	elif (item > vetor[meio]):

		inicio = meio + 1
		

	else :

		fim = meio - 1
		

return -1