Errors while doing Binary Search in Python . What is wrong with the code?

Question

import math 

def BinarySearch( A , val , low , high ):
    if high < low :
        return -1 #not found 
    mid = low + (high - low ) /2 
    if A[mid] > val:
        return BinarySearch(A,val , low , high )
    if A[mid] < val :
        return BinarySearch(A,val,low,high)
    else: 
        return mid #found 


A = [ 12 , 23 , 2 , 33 , 123 , 4 , 5 , 2 , 54 , 555 , 21 ]
BinarySearch( A , 0 , 0, 10)

I tried to do Binary Search without using the bisect Module . But it gives an error such as this

 File "doubtrob.py", line 8, in BinarySearch
    return BinarySearch(A,val , low , high )
RuntimeError: maximum recursion depth exceeded

Tauquir · Accepted Answer · 2011-02-03 12:04:43Z

3

def BinarySearch( A , val , low , high ):
    if high < low :
        return -1 #not found                                                                                                                                 
    mid = low + (high - low ) /2
    if A[mid] > val:
        return BinarySearch(A, val , low , mid-1 )
    if A[mid] < val :
        return BinarySearch(A, val, mid+1 ,high)
    else:
        return mid #found

recursion must have a end point. You are calling same parameters ever time so, it will never satisfy the high<low, so never terminates.

answered Feb 3, 2011 at 12:04

Tauquir

6,9437 gold badges39 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Marcelo Cantos · Accepted Answer · 2011-02-03 11:55:44Z

1

You are using exactly the same search space on each iteration. Also, you need to stop when high - low < 2, otherwise mid will eventually equal low, and you might still be stuck in an infinite loop.

As an aside, you can get mid more simply: (low + high)/2.

answered Feb 3, 2011 at 11:55

Marcelo Cantos

187k40 gold badges338 silver badges366 bronze badges

Comments

Y.H Wong · Accepted Answer · 2011-02-03 11:58:10Z

1

Hint: In the 2 return BinarySearch() calls, you keep calling it with the same parameters, so it keeps looping to the same spot on the next call, which keeps calling with the same parameters...

This is really a homework question. Hint Ends.

answered Feb 3, 2011 at 11:58

Y.H Wong

7,2443 gold badges36 silver badges35 bronze badges

Collectives™ on Stack Overflow

Errors while doing Binary Search in Python . What is wrong with the code?

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related