Binary search needs a sorted list. Compare the middle, then throw away half. Worst case is about log₂ n comparisons.

Goal

Search a sorted city list and print index plus steps versus linear search.

The loop

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

cities = ["Eldoret", "Kisumu", "Mombasa", "Nairobi", "Nakuru"]
print(binary_search(cities, "Nairobi"))
print(binary_search(cities, "Kericho"))

Alphabetical order: Eldoret < Kisumu < Mombasa < Nairobi < Nakuru.

Versus linear

def linear_search(items, target):
    steps = 0
    for i, item in enumerate(items):
        steps += 1
        if item == target:
            return i, steps
    return -1, steps

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

cities = ["Eldoret", "Kisumu", "Mombasa", "Nairobi", "Nakuru"]
print("linear", linear_search(cities, "Nakuru"))
print("binary", binary_search(cities, "Nakuru"))

Pitfall

Binary search on an unsorted list is wrong, not merely slow. Sort first, or do not use it.