Pesquisa Binária
A estratégia a adoptar neste algoritmo passa por comparar o elemento que procuramos com o valor do elemento armazenado no meio do vector.
* Se esse elemento for menor que o elemento do meio, então conclui-se que, se o elemento estiver presente no vector , ele estará na primeira parte do mesmo.
* Se o elemento a pesquisar for maior, então estará na segunda parte do vector. Logicamente que se for igual, estará encontrado o elemento do vector e a pesquisa ficará concluída.
* Se o elemento estiver estiver num das partes do vector, repete-se o procedimento considerando apenas a parte que restou e compara-se o elemento a procurar com o elemento de armazenado no meio dessa parte.
Em suma:
Há 3 tipos de comparações entre o elemento X a pesquisar e o valor v[i] que representa o valor posicionado no meio da estrutura de dados:
-> Se o X= V[i] então a pesquisa é bem sucedida. A pesquisa termina.
-> Se o X <V[i] então a pesquisa deve prosseguir na sub-lista dos elementos que procedem V[i], ou seja na primeira metade da lista.
-> Se X> V[i] então a pesquisa deve prosseguir na sub-lista dos elementos que sucedem V[i], ou seja na segunda metade da lista
Sem comentários:
Enviar um comentário