Complexity Analysis
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1What is the time and space complexity?
Work it out before scrolling down.
Time
O(log n)
Space
O(1)
How to derive it
Each iteration halves the search space. Starting with n elements: after 1 step → n/2, after 2 → n/4, ..., after k steps → n/2^k. We stop when n/2^k = 1, so k = log₂(n). Only three variables (lo, hi, mid) regardless of input size.