Métodos de Busca

BUSCA BINÁRIA

A busca binária é um conceito de estrutura de dados que descreve a busca de um determinado valor em um vetor ordenado, e que utiliza a divisão desse vetor em 2 partes a cada iteração (repetição). Uma das vantagens desse algoritmo é que todas as posições do vetor são testadas pois sua complexidade (tempo que o algoritmo demora para rodar) é na casa de (log n / log2), e a desvantagem mais importante é que para usar a busca binária, obrigatoriamente o vetor deve estar ordenado. Abaixo temos um exemplo da busca binária:

Temos um vetor de 10 posições ordenado e queremos fazer uma busca binária pelo número 8.
Vetor a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] A primeira repetição do algoritmo determinará o ponto central do vetor que é (9+0)/2 ou seja a posição 4,5 como é uma divisão inteira, posição 4. Então se verifica o número na posição 4 é 8, que desejamos encontrar. Como não é, o algoritmo divide o vetor em dois, uma metade da posição 0 até 4 e a outra da posição 5 até a 9. Então ele faz a seguinte pergunta, o número da posição 4 é maior ou menor que numero desejado (8), se maior você despreza a parte da direita, se menor você despreza a parte da esquerda. O algoritmo repete o processo até que o ponto central seja o número que ele está procurando ou que o vetor tenha apenas uma posição.

EXEMPLO DE CÓDIGO EM C++

Int PesquisaBinaria ( int *vetor, int chave, int N) { int inf = 0; int sup = n -1; int meio; while ( inf