Python binary search giving Wrong Answer in Moj

Asked

Viewed 246 times

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 in the ordered array and Q is the number of searches to be performed.

Second entry: Ordered array

Next Q entries: numbers to be searched.

For each search, you must return the position of the number in the vector (starting with 0) and, if not found, return -1

This is the link to the exercise in case anyone has doubts yet: http://www.spoj.com/problems/BSEARCH1/

python

  • Python 3+ or Python 2.7-? I say this because of input vs raw_input. Does it make any suggestions as to how it has to be resolved ? Binary search can be solved without recursion, which can imply that the same algorithm is tested for a larger input of values and fails for excessive time, for example

1 answer

0

At first, the only problem I’m seeing there is that you don’t test if a number isn’t found - if the number doesn’t exist, it will recur every time. Your program will eventually print the "-1" on the interactive terminal because Python will give a recursion limit error - but that’s a thousand function calls, when each of those would be 6 or 7 calls to find a result.

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

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

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

Browser other questions tagged python

You are not signed in. Login or sign up in order to post.