Binary search

items is sorted. Write binary_search(items, target) returning an index where target is, or -1.

Look at the middle. If the target is bigger, it can only be in the right half; if smaller, the left half. Each look halves what is left.

def binary_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

Run adds print(binary_search([1, 3, 5, 7, 9], 7)) after your code, to try it.

Stuck on the idea rather than the code? The Searching lesson walks through it.