1

Preciso criar uma função de busca binária. A função deve procurar o alvo na lista. verifica se lista[meio] é o numero que quero.Se for, retorna True. Se nao for, e o meio for maior, entao pode pegar um novo fim: meio-1 Se nao for, e o meio for menor, entao pode pegar um novo começo. Segue o código que estou tentando:

def busca_binaria(lista, alvo):
    ini = 0
    fim = len(lista)-1
    meio = (ini + fim)//2
    if alvo in lista:
        while alvo != lista[meio]:
            if lista[meio] > alvo:
                fim = meio-1
            else:
                ini = meio-1
        else:
            return True
    else:
        return False

Não sei pq não esta funcionando...não retorna...

1

2 Respostas 2

2

Vamos por partes...

Primeiro, se o seu objetivo é apenas retornar True se o elemento for encontrado, você não deveria estar usando o teste:

if alvo in lista: no seu código: esse é o jeito normal do Python de procurar elementos em listas, e ele já faz a busca retornando verdadeiro ou falso - e faz isso usando um algoritmo linear (embora faça isso "internamente", dentro do próprio runtime do Python). Daí nem adianta você fazer uma busca binária, por que já fez a operação mais lenta só pra começar sua busca binária - não adianta executar a busca rápida depois disso: só vai aumentar o tempo. E também, como você só retorna True ou False, e o Python já indicou que o elemento existe na lista, a busca perde o sentido: já sabemos a reposta antes dela começar.

Agora, o maior erro no código que você está tentando é que você só atualiza o meio fora da busca. Você atualiza o incio e o fim, ok, mas, não sei se você tem o costume de usar Excel, onde os valores das células com fórmulas são re-calculados automaticamente quando os valores de entrada usam, mas em programação imperativa - o estilo mais usado em programação com linguagens, inclsive em Python, isso não funciona assim - o valor de "meio" só é computado quando a linha

meio = (ini + fim)//2 

for executada - e isso só acontece antes de o programa entrar no seu laço while.

Por conta de você fazer a verificação de existência "por fora", naquele if alvo in lista, a lógica do seu while até está certa, quase que por coincidência, afinal ou o elemento é encontrado, ou é encontrado (sim ou sim :-) ) - e você nunca term que retornar um False depois que entrou no while. O que falha mesmo é que como o valor de "meio" nunca é atualizado, o programa vai ficar parado comparando o mesmo valor (e descobrindo que é falso) toda vez -- usando 100% de CPU e nunca encerrando a função.

Uma coisa que fica quase um detalhe aí, mas que é importante para você entender: embora o uso do else para o while não seja um erro de sintaxe em Python, ele é raramente usado - no caso ele só indica que o while foi terminado sem ser por um comando "break". Você poderia só retornar True ali sem o bloco de else, já que ele só sai do while quando achar o elemento buscado.

E por fim, nesse tipo de algoritmo, um ponto comum de erros é justamente escolher os pontos de início, fim e meio sem "errar por um" ao tentar fazer os ajustes de "comprimento - 1", e etc.. . A linguagem Python simplifica isso ao escolher, de forma elegante, que sempre que você pensa em sequências, o índice "final" indica onde a busca para - você não olha o elemento naquele índice. (então num vetor de comprimento "9", a busca é feita nos elementos nas posições de 0 até 8, naturalmente - o "meio" é "(0 + 9) // 2" => int(4.5) => 4". E tudo bem somar usar "meio -1 " e "meio + 1" para escolher os novos inicio fim. Perceba que justamente se "inicio == fim" e você não encontrou o número, quer dizer que o elemento não está na lista - nesse caso você retorna "False" (e nao precisa do "if elemento in lista").

resumindo: De tudo o acima, o mais importante é que o cálculo do meio precisa ficar dentro do while . Leia com atenção o restante para melhorar a coisa toda, mas entenda essa parte primeiro.

(em tempo - por questões obvias, não vou dar a resposta pronta - fique a vontade para entender o que está acima, refazer o seu código, e postar mais perguntas se for necessário)

0
1

Em primeiro lugar, o algoritmo de busca binária só funciona satisfatoriamente se a lista estiver ordenada. Em segundo lugar, percebi que você está tentando implementar um algoritmo de busca binária iterativa.

Pois bem, para implementarmos o algoritmo de busca binária iterativa devemos:

  1. Indicar a lista ordenada;
  2. Identificar o alvo;
  3. Identificar o início, tamanho e fim da lista;
  4. Criar uma fórmula para calcular o meio;
  5. Realizar as iterações pertinentes.
  6. Exibir o resultado.

Com esta lógica podemos implementar o seguinte código:

def busca_binaria_iterativa(lis, alv):
    ini = 0
    tam = len(lis)
    fim = tam - 1
    while ini <= fim:
        meio = ((ini + fim) // 2)
        if alv < lis[meio]:
            fim = meio - 1
        elif alv > lis[meio]:
            ini = meio + 1
        else:
            return True
    return False


lista = sorted(map(int, input('Digite os valores: ').split()))
alvo = int(input('Digite o valor a ser procurado: '))

print(busca_binaria_iterativa(lista, alvo))

Observe que quando executamos este código, recebemos a seguinte mensagem: Digite os valores: . Neste momento devemos digitar todos os valores da lista, na mesma linha, separados por um só espaço e pressionar Enter.

Tendo digitado todos os valores, os mesmos serão montados em uma lista, em ordem crescente. Em seguida, devemos digitar o valor a ser pesquisado e pressionar Enter. Depois destas operações a lista é passada como parâmetro para a função busca_binaria_iterativa().

Uma vez, o fluxo do programa chegando à referida função, serão definidas as seguintes variáveis: ini = 0, tam = len(lis) e fim = tam - 1.

A partir deste momento é iniciado a execução do bloco de repetição while. Então, neste momento, será verificado se ini <= fim. Caso positivo, será calculado o meio, através da fórmula: meio = ((ini + fim) // 2).

Observação 1

O meio deve ser implementado dentro do bloco while. Pois, esta variável será atualizada à cada iteração do while.

Observação 2

Para fins de eficiência e exatidão, no cálculo do meio utilizamos uma divisão inteira - "//" - e não uma divisão real - "/".

Após ter sido calculado o meio o fluxo do código entrará no bloco de decisões. Neste momento se alv < lis[meio], a variável fim será atualizada para o valor de meio - 1 e o bloco while será novamente executado. Caso alv > lis[meio], a variável ini será atualizada para o valor de meio + 1 e o bloco while será novamente executado. Caso contrário, ou seja, alv == lis[meio] a função encerra sua execução retornando o valor True.

Agora, depois de ter realizado todas as iterações e o valor alv não for encontrado, a função encerra sua execução retornando o valor False.

Testando o código

Imagine que a nossa lista seja [12, 15, 22, 37, 46, 51, 68, 73] e que desejamos pesquisar por um determinado valor. Então, executamos o código e, no momento que recebermos a mensagem: Digite os valores: , devemos digitar...

12 15 22 37 46 51 68 73

...e pressionar enter.

Em seguida devemos digitar o valor a ser pesquisado. Suponhamos que desejamos pesquisar pelo valor 37. Então, no momento que recebermos a mensagem: Digite o valor a ser procurado: , devemos digita...

37

...e pressionar enter.

A partir deste momento o código realizará todo o trabalho de pesquisa e nos retornará:

True

O retorno da função foi True porque, de fato, o valor 37 pertence à lista.

Agora, se o valor procurado não pertence à lista, o retorno da função será False.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .