Os Sistemas de Informação
Por: SonSolimar • 22/6/2018 • 890 Palavras (4 Páginas) • 298 Visualizações
...
5
6
7
8
GIL
IVO
LIA
RUI
Meio = (5+8)/2 = 6
↑
↑
↑
Esq
Meio
Dir
Como NEI > IVO, Esq = Meio + 1 = 6 + 1 = 7
7
8
LIA
RUI
Meio = (8+7)/2 =7
↑
↑
Esq, Meio
Dir
Como NEI > LIA, Esq = Meio + 1 = 7 + 1 = 8
8
RUI
Meio = (8+8)/2 =8
↑
Esq, Dir
Como NEI , Dir = Meio - 1 = 8 - 1 = 7
A nova partição (Meio = 8 e Dir = 7) é uma partição vazia porque meio>dir e, como não restam mais chaves, a pesquisa termina sem sucesso, ou seja, a chave NEI não foi localizada.
2. Verificar através da pesquisa binária se a chave “BIA” se encontra no vetor de registros ordenados segundo as chaves [ANA, BIA, CID, EVA, GIL, IVO, LIA, RUI]
Solução:
1
2
3
4
5
6
7
8
ANA
BIA
CID
EVA
GIL
IVO
LIA
RUI
Meio = (Esq+Dir)/2
↑
↑
↑
Meio = (1+8)/2 = 4
Esq
Meio
Dir
Como BIA , Dir = Meio -1 = 4 - 1 = 3
1
2
3
ANA
BIA
CID
Meio = (1+3)/2 = 2
↑
↑
↑
Esq
Meio
Dir
Como BIA = BIA, sucesso na busca.
3. Verificar através da pesquisa binária se a chave “IVO” se encontra no vetor de registros ordenados segundo as chaves [ANA, BIA, CID, EVA, GIL, IVO, LIA, RUI]
Solução:
1
2
3
4
5
6
7
8
ANA
BIA
CID
EVA
GIL
IVO
LIA
RUI
Meio = (Esq+Dir)/2
↑
↑
↑
Meio = (1+8)/2 = 4
Esq
Meio
Dir
Como IVO > EVA, Esq = Meio + 1 = 4 + 1 = 5
5
6
7
8
GIL
IVO
LIA
RUI
Meio = (5+8)/2 = 6
↑
↑
↑
Esq
Meio
Dir
Como IVO = IVO, sucesso na busca.
A seguir será ilustrada uma função de pesquisa binária (negrito) em um programa em C:
#include
#include
#define TAM 10
int p_binaria(int vet[TAM], int N){
int inicio=0;
int fim = TAM- 1;
int meio;
while
...