Lista exercícios de pesquisa sequencial e binária

Exercícios – Pesquisa

1) Implemente : O usuário deverá escolher um tipo de pesquisa (Menu)

1- Pesquisa sequencial

2- Pesquisa ordenada

3- Pesquisa binária

4- Sair

e também informar um número que será pesquisado.

Quando o usuário escolher a opção deverá ser executado a função do tipo da pesquisa selecionado. Utilize um vetor de inteiros com 16 elementos (utilize os valores do exemplo mostrado nos slides anteriores, não sendo necessário que o usuário entre com os 16 elementos). Mas lembre-se que para sequencial o vetor não está ordenado e na binária considere ele ordenado. O usuário deverá informar um número (chave) que será então realizado a pesquisa.

Informe ao final se encontrou (qual a posição) ou não o elemento procurado.

Caso a opção escolhida seja diferente do Menu acima informar que está incorreta a opção. O usuário poderá executar várias vezes .

2) Considere o vetor de 11 elementos abaixo e marque quantas comparações de igualdade serão necessárias para a pesquisa sequencial/linear, pesquisa ordenada e para pesquisa binária na tentativa de se encontrar os valores :  3, 25 e 70. Demonstre como você chegou a este resultado.

[pic 1]

3) Faça uma pesquisa sobre complexidade de algoritmos/tempo de execução (melhor caso, pior caso, caso médio) relacionados a pesquisa sequencial, ordenada e binária. Faça um resumo considerando o já estudado.

4) Considere a implementação realizada no exercício 1 e acrescente a informação da quantidade de comparações realizadas.

5) Inclua uma nova função que irá informar ao usuário as informações da pesquisa do exercício 3.

6) Uma loja de peças tem hoje 45000 peças em seu cadastro. Responda as questões abaixo, procurando demonstrar como você chegou aos resultados.

a) Se as peças estiverem ordenados qual seria a melhor pesquisa a ser aplicada ? Justifique sua resposta.

b) Considerando aplicar a busca binária nesta lista ordenada, quantos itens seria que ser examinado para encontrar a localização de uma peça no pior caso?

c) Considerando aplicar a busca binária nesta lista ordenada, quantos itens seria que ser examinado para encontrar a localização de uma peça no melhor caso?

d) Considerando aplicar a busca sequencial desordenada, quantos itens na lista, teria que ser examinado para encontrar a localização de uma peça?

e) Considerando aplicar a busca sequencial em uma lista ordenada, quantos itens seria que ser examinado para encontrar a localização de uma peça no melhor caso?

f) Considerando aplicar a busca sequencial em uma lista ordenada, quantos itens seria que ser examinado para encontrar a localização de uma peça no pior caso?

g) Considerando aplicar a busca sequencial em uma lista ordenada, quantos itens seria que ser examinado para encontrar a localização de uma peça no caso médio?

7) Max criou uma lista composta por cada um dos DDDs dos telefones encontrados no site da agência. Por exemplo, o conteúdo da lista seria [11,19,12,13,19,...]. A partir disso, Max gostaria de fazer uma função que recebe uma lista de inteiros (contendo um determinado telefone) e uma chave de busca com um inteiro. A função deve implementar o algoritmo de Busca Sequencial, retornando−1 se a chave não existir na lista, e  X caso ela exista, onde X é a posição (índice) da ocorrência do primeiro elemento da chave na lista.[pic 2][pic 3][pic 4]

Como exemplo de chamada da função busca_sequencial, considere o seguinte programa:

lista = [11, 19, 12, 13, 19, 43, 32, 41, 11, 12, 24]

chave = 12

pos = busca_sequencial (lista, chave)

if (pos == -1):

  print ("Não existe")

else:

  print ("Chave localizada na posição = ", pos)

Max faltou à aula em que foi ensinado o algoritmo de Busca Sequencial. Então ele ligou para seu amigo Joff que sugeriu que ele implementasse uma função com o algoritmo de Busca Binária — segundo ele mais eficiente que a busca sequencial. Você considera que é possível implementar a Busca Binária na situação descrita no programa dado?