Binary Search (recursive)
code: python
# O(logn), O()
def binary_search(arr, target, l, r):
if l <= r:
mid = (l + r) // 2
return mid
return binary_search(arr, target, mid+1, r)
else:
return binary_search(arr, target, l, mid-1)
else:
return -1
def test_binary_search():
assert binary_search(1, 2, 3, 4, 5, 6, 7, 8, 9, 6, 0, 8) == 5