Easy Binary Search Binary Search
In plain English: Look for a specific number in a sorted list by repeatedly cutting the search area in half.
Each comparison eliminates half the remaining elements — log2(n) halves is all you ever need to find any element or prove it absent.
Prompt
Given a sorted array and a target value, return the index of the target or -1 if not found.
Try to write it from scratch before scrolling down.
Solution
def binary_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == target:
return mid
elif a[mid] < target:
lo = mid + 1 # target is in right half
else:
hi = mid - 1 # target is in left half
return -1
# Test: binary_search([1,3,5,7,9,11], 7) == 3
# Test: binary_search([1,3,5,7,9,11], 4) == -1