1
def busca(num, a, primeiro, ultimo):
    meio = int((primeiro + ultimo) / 2)
    if num == a[meio]:
        return meio
    elif num < a[meio]:
        return busca(num, a, primeiro, meio)
    else:
        return busca(num, a, meio+1, ultimo)

arr = [int(x) for x in raw_input().split()]
tamArray = arr[0]
numQuery = arr[1]

arr = []
arr = [int(x) for x in raw_input().split()]

i = 0
while i < numQuery:
    num = int(input())
    try:
        print(busca(num, arr, 0, tamArray-1))
    except:
        print(-1)
    i += 1

Este é o código. A questão do moji pede as seguintes entradas: Primeira entrada: N e Q, sendo N a quantidade de numeros no array ordenado e Q a quantidade de buscas a serem realizadas.

Segunda entrada: Array ordenado

Próximas Q entradas: números a serem buscados.

Para cada busca, deve-se retornar a posição do número no vetor (começando com 0) e, caso não encontre, retornar -1

Este é o link do exercício caso alguem tenha ficado com dúvidas ainda: http://www.spoj.com/problems/BSEARCH1/

1
  • Python 3+ ou Python 2.7-? Digo isto devido ao input vs raw_input. Dá alguma sugestão face à forma como tem de ser resolvida ? Busca binária pode ser resolvida sem recursão, o que pode implicar que o mesmo algoritmo seja testado para uma entrada maior de valores e falhe por tempo excessivo, por exemplo
    – Isac
    9/11/2017 às 1:16

1 Resposta 1

0

A princípio, o único problema que estou vendo aí é que você não testa se um número não é encontrado - se o número não existir, ele vai fazer a recursão sempre . O seu programa eventualmente vai imprimir o "-1" no terminal interativo por que o Python vai dar um erro de limite de recursão - mas isso são mil chamadas de função, quando cada busca dessas seriam 6 ou 7 chamadas para encontrar um resultado.

Ponha uma condição a mais no seu if para retornar -1 direto da busca, quando o meio for igual ao início ou o fim do array, em vez de esperar um erro por limite de recursão.

Além disso tem algumas dicas de estilo: esse código está em Python 2 - se o servidor aceita Python 3 você deveria usar essa opção, (e aí é só trocar o "raw_input" por "input" - e tirar aquele "try ... except" que você já tem que fazer de qualquer forma: Python 3 não aceita um except: sem o tipo da exceção.

Mas -- você disse que o problema foi resposta errada, isso eu não consegui ver olhando o código.

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 .