Binary Search

Implement binary search returning the index of a target in a sorted list, or -1. Print the index for four targets and the number of comparisons for one of them.

0
4
9
-1

Keep lo and hi bounds; compare the middle and discard half each step.

def binary_search(values, target):
    lo, hi = 0, len(values) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

values = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
for t in (1, 9, 19, 8):
    print(binary_search(values, t))

Run your code to check it…