algoritmo de busca binaria

Análise e Desenvolvimento de
Sistemas

Estrutura de Dados

1

 Sequencial

(exaustiva)

 Binária

2

SEQUENCIAL:




A pesquisa sequencial é o método mais simples e intuitivo de pesquisa para uma variedade de estruturas de dados.
Embora possa ser utilizado com dados ordenados ou não, é mais utilizado quando os registros estão desordenados segundo a chave de pesquisa.

3

SEQUENCIAL:


A pesquisa é iniciada a partir do primeiro registro, avança sequencialmente (registro por registro) e termina quando for satisfeita uma das condições:

1. um registro com chave igual à pesquisada é encontrado e a pesquisa é concluída com sucesso.
2. todos os registros são analisados, mas nenhum deles possui chave igual à pesquisada e a pesquisa termina sem sucesso.

4

SEQUENCIAL:
Pseudo-código





Para cada item da lista, verifique se o elemento que você está procurando corresponde ao elemento atual.
Se for, retorne a posição que achou.
Senão, continue procurando até chegar no fim da lista.
Se chegou ao final da lista e não encontrou o elemento,ele não existe, então retorne -1.

5

SEQUENCIAL: código int buscaSequencial( int x, int n, int v[])
{
int m = 0; while (m < n && v[m] < x) ++m; if (m < n && v[m] == x) return m; else return -1;
}
6

7



No melhor caso, o registro com chave igual à procurada é encontrado na primeira posição, com apenas uma comparação. 

No pior caso, de pesquisa bem sucedida, o registro é localizado na posição N, com um custo de N comparações.



No caso médio, o número de comparações para localizar o registro é a média entre o pior e o melhor caso, ou seja,
(N+1)/2. Portanto, a complexidade da pesquisa sequencial cresce linearmente com o tamanho do vetor, o que não é nenhuma surpresa.
8

Pesquisa Binária

9

Pesquisa Binária:


É uma forma mais eficiente de realizar pesquisas em relação ao método de PS.
Metodologia:
• Consiste em