Segmentation fault: 11 / RecursionError: maximum recursion depth exceeded while calling a Python obj-CodePudding

for my project, I am coding a binary search function (this is my first project!) However, when I try to implement a list that is >= 10, I get the recursion error. By looking at some answers in this site, I've roughly learned and am assuming python sets a recursion limit so that it will prevent stack overflow. So I implemented someone's solution:

import sys  
sys.setrecursionlimit(100000)

which lead to the following error:

Segmentation fault: 11

Here is my code:

import random
import time
import sys  
sys.setrecursionlimit(100000)

# Implementation of binary search algorithm

# Proving that binary search is faster than naive search

# naive search: scan entire list and ask if it's equal to the target
# if yes, return index
# of no, then return -1 
def naive_search(l,target):
    # example l = [1,3,5,10,12]
    for i in range(len(l)):
        if l[i] == target:
            return i
    return -1
        

# binary search: devide and conquer 
# Leveraging the fact that our list is sorted 
def binary_search(l,target,low = None, high = None):
    if low is None:
        low = 0
    if high is None:
        high = len(l) - 1 
    if high < low:
        return -1

    # example l = [1,3,5,10,12] # should return 3 
    midpoint = (low   high) // 2  # 2
    
    if l[midpoint] == target:
        return midpoint
    elif target < l[midpoint]:
        return binary_search(l, target,low = None, high = midpoint - 1) 
    else:
        # target > l[midpoint]
        return binary_search(l, target, low = midpoint   1, high = None)

    
if __name__ ==  '__main__':
    
    l = [1, 3, 5, 10, 12, 15, 35, 40, 45]
    target = 10
    print(naive_search(l,target))
    print(binary_search(l,target))
    
"""
    length = 10
    # build a sorted list of length 1000
    sorted_list = set()
    while len(sorted_list) < length:
        sorted_list.add(random.randint(-3*length, 3*length)) 
    sorted_list = sorted(list(sorted_list))   
    print(sorted_list)
""" 
"""
    l = sorted_list
    target = 10
    print(binary_search(l,target))
"""

The youtube tutorial that I looked didn't have this problem so I'm really confused. https://www.youtube.com/watch?v=8ext9G7xspg&t=9094s @ 1:26:00 Thank you for your time.

CodePudding user response：

Method 1

The issue lies in the recursive calls:

    elif target < l[midpoint]:
        return binary_search(l, target,low = None, high = midpoint - 1) 
    else:
        # target > l[midpoint]
        return binary_search(l, target, low = midpoint   1, high = None)

You want to copy the low, and high rather than setting them to None. The correct call should be:

    elif target < l[midpoint]:
        return binary_search(l, target,low = low, high = midpoint - 1) 
    else:
        # target > l[midpoint]
        return binary_search(l, target, low = midpoint   1, high = high)

To demonstrate the bug:

Using your example, in the original call: low=0, high=8

Then, in the 1st recursion, low=0, high=4.

Now, target=10 > midpoint=5, you code makes the following call

binary_search(l, target, low = midpoint   1, high = None)

Since high=None, it will be set to high=8 in the next recursion, giving you low=3, high=8. This is not what you want, since you already eliminated the top half. So you need to carry over low and high in the recursive call rather than setting them to None.

To be more efficient, you can also check l[low] and l[high] in addition to l[midpoint] against the target.

Method 2

Alternatively, you can give a subset of the list in the recursive call. Then, you don't really need the low and high argument any more. Since slicing only generate new references rather than copies, it doesn't have too much impact on memory.

    elif target < l[midpoint]:
        return binary_search(l[low:midpoint], target,low = None, high = None) 
    else:
        # target > l[midpoint]
        return binary_search(l[midpoint 1:high 1], target, low = None, high = None)