Busca linear busca binária

Busca
Busca em Vetores
• Esta aula introduz a busca em vetores que está entre as tarefas mais freqüentemente encontradas em programação de computadores
• Serão abordados dois tipos de busca: linear (ou seqüencial) e binária
Prof. Dr. José Augusto Baranauskas
DFM-FFCLRP-USP
• A hipótese básica assumida no processo de busca é que o conjunto de dados, dentre o qual um determinado elemento deve ser procurado, possui tamanho fixo, ou seja, um vetor: item a[N];
• onde item representa uma estrutura de dados contendo um campo que atua como chave para a pesquisa e N é uma constante indicando o número de elementos typedef struct
{ int key;
// chave de busca
...
// demais campos da estrutura
} item;
• Objetivo da busca: dado x encontrar a[i].key == x
• O índice i resultante permite acesso aos demais campos
1
2
Busca Exemplo
• Para estudo, vamos admitir que o tipo item seja • composto apenas do campo chave, ou seja, o dado • é a própria chave. • • Além disso, para facilitar o estudo ainda mais, a • chave de busca será um inteiro, ou seja, o vetor a será declarado como:
Busca de x = 19, retorna i = 5
Busca de x = 45, retorna i = 0
Busca de x = 8, retorna i = 6
E a busca de x = 81?
0
int a[N]; a 1 2 3 4 5 6 7
45 56 12 43 95 19 8 67
• Lembrando que N é uma constante que indica o número de elementos do vetor
• Assim, objetivo da busca se resume a dado x encontrar a[i] == x
3
4
Exemplo Busca Linear (ou Seqüencial)
• • • • •
Busca de x = 19, retorna i = 5
Busca de x = 45, retorna i = 0
Busca de x = 8, retorna i = 6
E a busca de x = 81?
•
1. O elemento é encontrado, isto é, a[i] == x
2. Todo o vetor foi analisado, mas o elemento x não foi encontrado
•
0 a Utilizada quando não há de informações adicionais sobre os dados a serem pesquisados
A busca linear termina quando for satisfeita uma das duas condições seguintes:
1 2 3 4 5 6 7
45 56 12 43 95 19 8 67
• Depende da