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.
Segundo a Wikipédia um algoritmo de busca é um algoritmo que toma um problema como entrada e retorna à solução para a problemática, geralmente para resolver um número possíveis de soluções. 
Quando os itens de dados estão dispostos em uma coleção, como uma lista, dizemos de eles tem uma relação linear ou sequencial, cada item é armazenado em uma posição relativa a outros, é realizada a comparação elemento por elemento, de modo que a função do tempo em relação ao número de elementos é linear, cresce proporcionalmente, assim os algoritmos de busca sequencial são utilizados para sequência de dados desordenados,
No melhor caso, o elemento as ser buscado é encontrado logo na primeira tentativa de busca e no pior caso será encontrado na ultima posição e são feitas N comparações, no caso médio o elemento é encontrado após (N+1)/2 comparações.
A busca binária é a melhor opção para um vetor ordenado ele funciona dividindo repetidamente pela metade a porção da lista que deve conter o elemento buscado segue o paradigma de divisão e conquista. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.
A complexidade desse algoritmo é da ordem O(log2n)[1], em que n é o tamanho do vetor de busca. Apresenta-se mais eficiente q1ue a Busca linear cuja ordem é O(n)[2]
Referências:
https://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria
https://pt.wikipedia.org/wiki/Busca_linear
https://www.mundojs.com.br/2018/02/05/algoritmos-de-busca-sequencial-e-binaria/