-2

I am trying to apply the Binary Search algorithm (the recursive way) and I'm having this error

def BinarySearchRec(tab, x):
    mid = len(tab) // 2
    if len(tab) == 0:
        return False
    if tab[mid] > x:
        return BinarySearchRec(tab[:mid], x)
    elif tab[mid] < x:
        return BinarySearchRec(tab[mid:], x)
    else:
        return mid

I tried to 1 and retrive one when i call the function back but didn't work on all cases

Mechanic Pig
  • 6,756
  • 3
  • 10
  • 31
Blem.Hamza
  • 1
  • 1
  • 1
    Please update your question with an example of how you call your function when it exceeds maximum recursion depth. – quamrana Nov 19 '22 at 14:44
  • Add a print statement or use a debugger to monitor the value of `mid` from call to call. You'll see that `tab[:mid]` and `tab[mid:]` eventually are the same as `tab`, so your recursion isn't progressing. – chepner Nov 19 '22 at 14:44
  • 2
    When the length of the list is 1 and you try to slice `tab[mid:]`, you will get the same list, which causes the recursion to fail. – Mechanic Pig Nov 19 '22 at 14:48
  • 1
    Welcome to Stack Overflow. "I tried to 1 and retrive one when i call the function back but didn't work on all cases" This isn't understandable. Please read [ask] and [mre], and clearly show: how do you call the function in order to cause a problem? What should happen for that input? What does happen instead, and how is that different? – Karl Knechtel Nov 19 '22 at 15:23

1 Answers1

1

When mid=0 and tab[mid] < x, the code gets stuck because BinarySearchRec(tab[mid:], x) will loop forever with the same inputs: (tab[mid:],x) -> (tab[0:],x) -> (tab,x) .

As a proof, you can try the following example:

tab = [1]
x   = 2
BinarySearchRec(tab, x)
# recursion error raised

The easiest solution is to make sure that the array tab decreases in size every time you perform recursion:

def BinarySearchRec(tab, x):
    mid = len(tab) // 2
    if len(tab) == 0:
        return False
    if tab[mid] > x:
        return BinarySearchRec(tab[:mid-1], x)
    elif tab[mid] < x:
        return BinarySearchRec(tab[mid+1:], x)
    else:
        return mid

tab = [1]
x   = 2
BinarySearchRec(tab, x)
# now it works

In the new code, the tab array is trimmed using either mid+1 or mid-1, since we can discard mid as a solution when tab[mid] != x. This makes sure that tab always decreases at least one element in size, and hence the code does not crash. Cheers,

C-3PO
  • 1,181
  • 9
  • 17