Binary search in python giving wrong answer in Moj

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

This is the code. The moji question asks for the following entries: First entry: N and Q, where N is the number of numbers in the sorted array and Q the number of searches to perform.

Second entry: Array ordered

Next Q entries: numbers to look for.

For each search, return the position of the number in the vector (starting with 0) and, if it does not find it, return -1

This is the link for the exercise if anyone has any questions: link

    
asked by anonymous 09.11.2017 / 01:49

1 answer

0

At first, the only problem I'm seeing there is that you do not test if a number is not found - if the number does not exist, it will always do the recursion. Your program will eventually print the "-1" in the interactive terminal because Python will give a recursion limit error - but that's a thousand function calls, when each search of those would be 6 or 7 calls to find a result. / p>

Put one more condition in your if to return -1 straight from the search, when meio is equal to the beginning or end of the array, instead of waiting for a recursion limit error.

In addition you have some style tips: this code is in Python 2 - if the server accepts Python 3 you should use this option, (and then just change "raw_input" to "input" - and take that "try ... except "you already have to do it anyway: Python 3 does not accept a except: without the exception type.

But - you said that the problem was wrong answer, this I could not see by looking at the code.

    
09.11.2017 / 13:37