Need help to fix a Recursive Binary Search Function in Python

Question

When I run this function (by taking lower and upper bounds as 0 and len(list)-1), it works fine. But when the key is not there in the search_list I get a bad error. Any way to fix this so it says that the name/key was'nt found in the list?

def binary_search_recursive(search_list, key, lower_bound, upper_bound):
    middle_pos = (lower_bound + upper_bound) // 2
    if search_list[middle_pos] < key:
        binary_search_recursive(search_list, key, middle_pos + 1, upper_bound)
    elif search_list[middle_pos] > key:
        binary_search_recursive(search_list, key, lower_bound, middle_pos - 1)
    else:
        print('Key is at Position', middle_pos)

Mark · Accepted Answer · 2019-04-07 17:18:29Z

1

You need to address the edge condition that occurs when the lower bound is greater than the upper bound and return from the function. This means the value was not found.

def binary_search_recursive(search_list, key, lower_bound, upper_bound):
    if lower_bound > upper_bound: # not found
        print("not found")
        return
    middle_pos = (lower_bound + upper_bound) // 2
    if search_list[middle_pos] < key:
        binary_search_recursive(search_list, key, middle_pos + 1, upper_bound)
    elif search_list[middle_pos] > key:
        binary_search_recursive(search_list, key, lower_bound, middle_pos - 1)
    else:
        print('Key is at Position', middle_pos)

binary_search_recursive([1, 2, 3, 4, 5], 6, 0, 4)

not found

edited Apr 7, 2019 at 17:18

answered Apr 7, 2019 at 17:12

Mark

92.6k8 gold badges116 silver badges156 bronze badges

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

1 Comment

Heitor Boschirolli Over a year ago

shouldn't be if lower_bound > upper_bound? If the list has just one element wouldn't your function print "not found" even if the single element is the key?

Collectives™ on Stack Overflow

Need help to fix a Recursive Binary Search Function in Python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related