Algoritmo de Pesquisa Binária em Array

Prévia do material em texto

ESTRUTURA DE DADOS
PROF. MSC. ALLAN KÁSSIO BECKMAN SOARES DA CRUZ
PESQUISA BINÁRIA E ALGORITMOS 
DE CLASSIFICAÇÃO
PESQUISA LINEAR
 O algoritmo de pesquisa linear pesquisa cada elemento em um 
array sequencialmente. 
 Se a chave de pesquisa não corresponder a um elemento no 
array, o algoritmo testa cada elemento e, quando alcança o fim 
do array, informa o usuário que a chave de pesquisa não está 
presente.
 Se a chave de pesquisa estiver no array, o algoritmo testa cada 
elemento até encontrar um que corresponda à chave de 
pesquisa e retorna o índice desse elemento.
PESQUISA LINEAR
PESQUISA BINÁRIA
 É mais eficiente que o de pesquisa linear,
 Exige que o array seja classificado. 
 A primeira iteração desse algoritmo testa o elemento no meio do array. 
 Se isso corresponder à chave de pesquisa, o algoritmo termina. 
 Supondo que o array seja classificado em ordem crescente, se a chave de pesquisa for menor 
que o elemento do meio, ela não poderá localizar nenhum elemento na segunda metade do 
array e o algoritmo continua com apenas a primeira metade do array (isto é, até o primeiro 
elemento, mas sem incluir o elemento do meio). 
 Se a chave de pesquisa for maior que o elemento no meio, ela não poderá localizar nenhum 
elemento na primeira metade do array e o algoritmo continua apenas com a segunda metade 
(isto é, o elemento depois do elemento do meio até o último elemento). 
 Cada iteração testa o valor do meio da parte restante do array. 
 Se a chave de pesquisa não corresponder ao elemento, o algoritmo eliminará 
metade dos elementos restantes. 
 O algoritmo termina localizando um elemento que corresponde à chave de pesquisa 
ou reduzindo o subarray ao tamanho zero.
PESQUISA BINÁRIA
PESQUISA BINÁRIA
PESQUISA BINÁRIA
PESQUISA BINÁRIA
Implemente um algoritmo 
que realize a pesquisa 
binária no array 
 [13, 18, 29, 36, 42, 47, 56, 57, 63, 68, 80, 81, 82, 88, 88]
PESQUISA BINÁRIA