Algoritmos de Busca Sequencial e Binária

Prévia do material em texto

Caro, aluno,
Ao longo da Unidade foram abordados: a problemática do crescimento do volume de dados; conceitos e técnicas sobre algoritmos de busca, ordenação e armazenamento; bem como análise de complexidade.  Os referidos algoritmos são recursos importantes que possibilitam melhor aproveitamento da grande quantidade de informação armazenada nos repositórios de dados. Estes assuntos proporcionaram a você uma ampla visão sobre o tema, sua aplicabilidade e importância no cenário tecnológico atual. (MANZANO, J. A. N. G.; LOURENÇO, A. E.; MATOS, E. Algoritmos - Técnicas de Programação.  2. ed. São Paulo: Érica, 2015.)
Com base no material que você estudou, escreva sobre algoritmos de busca sequencial e binária, dando exemplos e buscando apresentar as diferenças.
Algumas simples ações do dia a dia, como por exemplo trocar uma lâmpada, fazer um bolo, tomar banho, exigem do indivíduo um padrão de procedimentos a serem seguidos para a sua ação. Com isso, podemos considerar que essas ações são algoritmos do nosso cotidiano. Para a prática de algoritmos, temos a busca binária e linear (sequencial).
Uma busca binária começará examinando o item do meio. Se esse item for aquele que estamos procurando, a busca termina. Se não for o item correto, podemos usar a natureza ordenada da lista para eliminar a metade dos itens restantes. Como exemplo, numa busca por uma determinada estrela de uma galáxia, num banco de dados ordenado com milhares de estrelas, usando a busca binária podemos reduzir à metade uma busca que seria feita por completo, do início ao fim. A busca binária é um algoritmo um pouco mais sofisticado.  E mais eficiente, mas requer que o vetor esteja ordenado pelos valores da chave de busca.
A busca sequencial é o algoritmo mais simples de busca:
1 - Percorra todo o vetor comparando a chave com o valor de cada posição.
2 - Se for igual para alguma posição, então devolva esta posição.
3 - Se o vetor todo foi percorrido então devolva -1.
Um exemplo prático da busca sequencial pode ser observado na busca por um arquivo em uma pasta. Dentro da pasta será buscado o nome do arquivo desejado, em todas as posições existentes. Caso seja encontrado, o valor será exibido ao usuário, e caso não seja encontrado, o valor negativo será devolvido ao usuário, dando o resultado de “não encontrado”.