Visual Walkthrough of Binary Search

binary_search.py

from typing import List


def binary_search(numbers: List[int], key: int):
    mid = 0
    low = 0
    high = len(numbers) - 1
    iteration = 0

    while high >= low:
        mid = (high + low) // 2
        print("Iteration {}".format(iteration))
        print("  low: {}".format(low))
        print("  mid: {}".format(mid))
        print("  high: {}".format(high))

        if numbers[mid] < key:
            print('  -> numbers[{}] = "{}" and is < {}'.format(mid, numbers[mid], key))
            low = mid + 1
        elif numbers[mid] > key:
            print('  -> numbers[{}] = "{}" and is > {}'.format(mid, numbers[mid], key))
            high = mid - 1
        else:
            print("-> Found {} at index {}".format(key, mid))
            return mid
        iteration += 1
        print()

    return -1


if __name__ == "__main__":
    numbers = [2, 4, 7, 10, 11, 32, 45, 87]
    i = 0
    key = 0
    keyIndex = 0

    print("NUMBERS: {}".format(numbers))
    key = int(input("Enter a value to search for: "))

    keyIndex = binary_search(numbers, key)

    if keyIndex == -1:
        print(str(key) + " was not found.")
    else:
        print("Found " + key + " at index " + keyIndex + ".")