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