1

Olá, eu quero criar uma função que dado uma lista a e um valor m dentro desta lista, retorne a posição do valor m. A minha ideia era começar com os valores extremos da lista ordenada e pegar o ponto médio até encontrar o valor m (e então retornar sua posição):

def bissecp(a,m):

    n = len(a) - 1

    i=0

    encontrou = False

    meio = int(((a[i] + a[n]) / 2))

    if m==a[i]:
        return i
    if m==a[n]:
        return n
    index = 0
    if m == meio:
        encontrou == True
        return int((i+n)/2)
    while encontrou == False:
        if m> meio:
            i+=1
            meio = int((a[i] + a[n])/2)
            if m == meio:
                 index = int((i+n)/2)
                 encontrou==True
            continue
        if m < meio:
            i += 1
            meio = int((a[i] + a[n-i]) / 2)
            if m == meio:
                index = int((a[i] + a[n-i])/2)
                encontrou==True

    return index


a = list(range(1, 100))

mas está retornando o seguinte erro :

Traceback (most recent call last):
  File "<input>", line 1, in <module>
  File "<input>", line 28, in bissecp
IndexError: list index out of range

2 Respostas 2

3

O maior problema na sua tentativa é que você está fazendo:

meio = int(((a[i] + a[n]) / 2))

Isso pega o elemento de "a" na posição "i", e o elemento de a na posição "n" e tira a média - Quando você deveria estar pegando é o elemento de "a" que está na posição (i + n) // 2. Sua variável "meio" é um número que possivelmente nem está na lista - não faz sentido comparar ele com o número que está sendo buscado, na variável m. Pode ter funcionado em alguns casos por que você passou um range, que vai de "1" em "1", mas se passar uma lista com números aleatórios, em ordem crescente, vai ficar ainda mais maluco.

Uma outra dica para te ajudar: não tem por que economizar letras nos nomes de variáveis - isso só deixa o código mais difícil de ler. Por que "a" e "m"? Dá pra chamar de "lista" e "alvo". Daí você compara um "elemento da lista, no índice computado" com o "alvo": if lista[index] == alvo: encontrou = True.

Eu não vou sugerir pequenas modificações no seu programa, por que essa confusão de índice com o conteúdo deixa o mesmo bastante errado - tenha essas dicas em mente, e tente re-fazer o programa (vai ser mais fácil do que tentar arrumar esse código).

A última dica é que esse erro específico acontece por que em algum ponto você tenta recuperar um elemento da lista "a" que está para além do comprimento dela. Se o algoritmo estivesse correto, isso nunca aconteceria - os índices sempre vão se movendo pra dentro da lista. Mas como você está atualizando os índices de forma praticamente arbitrária, misturando os índices com o conteúdo da lista, não tem nada que garanta que o valor seja comportado.

Para ter uma lista de valores malucos crescentes, que você possa testar pode fazer usar o random.choices:

In [421]: import random                                                                                                

In [422]: lista = sorted(random.choices(range(1000), k=10))                                                            

In [423]: lista                                                                                                        
Out[423]: [54, 73, 186, 279, 480, 508, 572, 589, 707, 845]
1

O algoritmo desejado na pergunta é de busca binária. Algoritmo de bissecção é um algoritmo para obtenção de raízes, também conhecido como pesquisa binária e daí talvez a confusão.

O algoritmo de busca binária pode ser implementado da seguinte forma:

def bb(a,m):

    esq = 0
    dir = len(a) - 1

    while esq <= dir:

        meio = (esq + dir) // 2  # operador // significa divisão inteira (truncada)

        if a[meio] == x:
            return meio
        elif x < a[meio]:
            dir = meio - 1
        elif x > meio:
            esq = meio + 1

    return -1 # retorna -1 se o elemento não foi encontrado


a = list(range(1, 100)) # não inclui o valor 100

x = int(input("Elemento a ser buscado: "))

localizacao = bb(a, x)

if localizacao == -1:
    print("Elemento não encontrado.")
else:
    print("Localização do elemento: " + str(localizacao) + ".")  # localizacao comecando em 0

Caso queira ler uma lista ordenada ao invés de gerar um range, utilize o seguinte código:

input_string = input("Entre a lista crescente de inteiros separados por espaços: ")
a  = [int(item) for item in input_string.split()]

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 .