6. Algoritmos de Busca

Você certamente já realizou algum tipo de pesquisa por algum elemento que satisfaça uma condição desejada. Considere agora o seguinte problema: é preciso encontrar um nome em uma lista telefônica. Sair folheando as páginas indiscriminadamente seria uma atitude pouco eficaz. De forma instintiva, procuramos o nome abrindo a lista aproximadamente na metade, um pouco mais, ou pouco menos, de acordo com a inicial do nome. Se os nomes que aparecem têm suas iniciais maiores que a do nome que estamos procurando, imediatamente dividimos as folhas da esquerda e, caso contrário, dividimos as folhas da direita. Essa operação de dividir a lista é realizada até que nos tenhamos aproximado do nome desejado e, assim podemos folhear as páginas para encontrá-lo. Esse é um método muito eficaz para realizar uma pesquisa, mas, para isso, as informações devem estar ordenadas.

Procurar informações em um conjunto desordenado demanda uma operação pouco produtiva, pois é preciso “olhar” cada um dos elementos até encontrar o desejado e, caso ele não exista, todos os elementos terão sido consultados.

Buscar é uma atividade com a finalidade de encontrar se existe ou não elementos em um conjunto. Nesta seção, serão apresentados alguns algoritmos de busca em um conjunto de dados ordenado: busca sequencial e busca binária. A eficiência de cada um está na posição em que o dado pesquisado se encontra, o que poderá ser avaliado após conhecer os algoritmos.

Objetivos

• Identificar a estruturação de pesquisas para se obter a informação desejada no menor tempo possível;

• Reconhecer a importância do ordenamento de dados;

• Elaborar a implementação de alguns algoritmos de busca como a busca sequencial e a busca binária em conjunto de dados ordenado