Binary search divides the search space in half with each comparison.
Base case: When left > right, the target isn't in the list. Return .
Recursive case: Calculate the middle index, compare, then recurse on the appropriate half.
def binary_search(lst, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if lst[mid] == target:
return mid
if target < lst[mid]:
return binary_search(lst, target, left, mid - 1)
return binary_search(lst, target, mid + 1, right)
This runs in time and uses space for the call stack.