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/
input
vsraw_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