Pesquisa binária

CENTRO UNIVERSITÁRIO CARIOCA – UNICARIOCA
Michel de Medeiros – 2013101433
Elen Pereira - 2013201851
Rodrigo Simões - 2013202179

Busca Binária

RIO DE JANEIRO
2013
Michel de Medeiros – 2013101433
Elen Pereira - 2013201851
Rodrigo Simões - 2013202179

Busca Binária

Trabalho de Busca Binária, apresentado ao Centro Universitário Carioca, como requisito parcial para Estrutura de Dados I.

Prof. Anderson Fernandes Pereira dos Santos

RIO DE JANEIRO
2013

SUMÁRIO

1 INTRODUÇÃO
1.1 Busca binária é um conceito de estrutura de dados que descreve a busca de um determinado valor em um array ordenado, que utiliza a divisão do array em duas partes a cada iteração.
Esse algoritmo tem uma vantagem enorme. frente a busca linear onde todas as posições do array são testadas pois sua complexidade (tempo que o algoritmo demora para rodar) é na casa de (log n / log2) (log de n na base 2), enquanto a da busca linear é n, sendo n a quantidade de posições do array.
Uma explicação melhor da busca binária precisa de exemplos:
Temos um array (vetor) de 10 posições ordenado e queremos fazer uma busca bináriapelo número 8.

vetor a = [0,1,2,3,4,5,6,7,8,9]
A primeira iteração do algoritmo determinará o ponto central do array que é (9 + 0)/2 ou seja a posição 4,5 como é uma divisão inteira posição 4.
Então verifica-se se o número na posição 4 é 8, que desejamos encontrar.
Como não é, o algoritmo divide o array em dois, uma metade da posição 0 até 4 e a outra da posição 5 até a 9.
Então ele decide qual dessas partes desprezar e em qual se manter procurando. Para isso ele compara o número que está procurando com o valor no ponto central, se o ponto central for maior que o número ele manterá a primeira metade, e desprezará a segunda metade. Se o número central for menor que o valor no ponto central, ele desprezará a primeira metade e manterá a segunda.