Algoritmo de Busca em C

Método de Busca

• O problema da busca (ou pesquisa) - Dado um conjunto de elementos, onde cada um é identificado por uma chave, o objetivo da busca é localizar, nesse conjunto, o elemento que corresponde a uma chave específica. • Vários métodos e estruturas de dados podem ser empregados para se fazer busca.
• Certos métodos de organização/ordenação de dados podem tornar o processo de busca mais eficiente 1

TIPO DE BUSCA
O conjunto de registros pode ser:
• Um vetor de registros
• Uma lista encadeada
• Uma árvore
• Etc.
O conjunto de registros pode ficar:
• Totalmente na memória (busca interna)
• Totalmente no armazenamento auxiliar (busca externa) • Dividida entre ambos

TIPO DE BUSCA
1. Busca Seqüencial
2. Busca Binária
3. Arvore de Busca Binária
4. Hash

2

BUSCA SEQUENCIAL
Compara a chave com cada item na array ou lista, até encontrar um item de dado cujo valor é igual o valor da chave.

Coleção de Dados:
10 3 16 0

-1 104

23 -7 88

6

4

1000

Chave: 0
Exercício: Escreve uma função de busca seqüencial em C.

BUSCA SEQUENCIAL
Algoritmo de busca seqüencial em um vetor A, com
N posições (0 até N-1), sendo x a chave procurada for (i=0; i high then return NIL; mid = (high+low)/2; if k = key[mid] then return key[mid]; else if k < key[mid] then return Bin_search(c, low, mid-1, k); else return Bin_search(c, mid+1, high, k);

8

BUSCA BINÁRIA
Complexidade?
- O(log(n)), pois cada comparação reduz o número de possíveis candidatos por um fator de 2.

ÁRVORES DE BUSCAS BINÁRIAS
Arvore de busca binária é representada por uma estrutura de dados ligada. Cada nó contem 4 campos:
• key: valor do nó;
• left: ponteiro que aponta para seu filho esquerdo;
• right: ponteiro que aponta para seu filho direito;
• p: ponteiro que aponta para seu pai.

9

2
5
3
7

3
2

7
8

5

5

8

5
PROPRIEDADE:
Suponho que x é um nó da arvore de busca binária, para qualquer nó y, se y está na