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)

Answer 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

• Heitor Boschirolli: 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?