I'm working on a recursive binary search for school. Because of the test code, I'm limited to my input being lyst
and target
and output should only be a bool
asserting whether the target was found or not. I've found examples of other questions kind of like mine, but they usually resort to having the upper and lower bounds as part of the input. I can't do that apparently. I'm also unsure as to whether or not I can use a helper function. I will try to find out. This is what I have so far:
def binary_search(lyst, target):
left = 0
right = len(lyst) - 1
while left <= right:
mid = (right left) // 2
if len(lyst) == 0:
return False
elif lyst[mid] < target:
left = mid
return binary_search(lyst[left: right], target)
elif lyst[mid] > target:
right = mid
return binary_search(lyst[left: (right 1)], target)
elif lyst[mid] == target:
return True
return False
It works for some cases, but not all. For example, it will find target of 3 in in the following list my_list = [1,2,3,4,5,6,7,8,9,10]
, but will not find three in a list of 1-15. I feel like I'm close, but could use a little help.
CodePudding user response:
Since recursion is not a requirement, you can just keep track of the start and end indices and stop when they've squeezed together. This avoids the slices while also allowing the function signature to remain unchanged:
def binary_search(lyst, target):
start = 0
end = len(lyst)
while start < end:
mid = (end - start) // 2 start
if lyst[mid] == target:
return True
if target < lyst[mid]:
end = mid
else:
start = mid 1
return False
my_list = [1,2,3,4,5,6,7,8,9,10, 11, 12, 13, 14, 15]
print(binary_search(my_list, 3))
# True
# Some edge cases:
print(binary_search([1], 3))
# False
print(binary_search([], 3))
# False
print(binary_search([3], 3))
# True
print(binary_search([1, 3], 3))
# True
If you still want to use recursion with slices you don't need the loop, the recursion takes the place. Everything else is very similar, but in this case you need to deal with the edge case where recursion should stop:
def binary_search_rec(lyst, target):
if not lyst:
return False
mid = len(lyst) // 2
if lyst[mid] == target:
return True
if target < lyst[mid]:
return binary_search_rec(lyst[:mid], target)
else:
return binary_search_rec(lyst[mid 1:], target)
of course, as mentioned in the comments, you loose the efficiency because you need to create new lists with each call.