#!/usr/bin/python3
# -*- coding: utf-8 -*-

from typing import Optional


def binary_search(numbers: list[int], key: int) -> Optional[int]:
    low: int = 0
    high: int = len(numbers)
    while low < high:
        mid = (high + low) // 2
        if numbers[mid] < key:
            low = mid + 1
        elif key < numbers[mid]:
            high = mid - 1
        else:
            return mid
    return None


def main() -> None:
    numbers: list[int] = [2, 4, 7, 10, 11, 32, 45, 87]
    print("NUMBERS: ", numbers)
    key = int(input("Enter a value: "))
    # This takes O(n)
    keyIndex = binary_search(numbers, key)
    if keyIndex is None:
        print(key, " was not found")
    else:
        print("Found ", key, " at index ", keyIndex)


if __name__ == "__main__":
    main()