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

from typing import List


def binary_search(numbers: List[int], key: int) -> int:
    low: int = 0
    high: int = len(numbers)
    mid = (high + low) // 2

    while high >= low and numbers[mid] != key:
        mid = (high + low) // 2

        if numbers[mid] < key:
            low = mid + 1
        elif numbers[mid] > key:
            high = mid - 1

    if numbers[mid] != key:
        mid = -1

    return mid


def main() -> None:
    numbers: List[int] = []
    numbers.append(2)
    numbers.append(4)
    numbers.append(7)
    numbers.append(10)
    numbers.append(11)
    numbers.append(32)
    numbers.append(45)
    numbers.append(87)

    print("NUMBERS: ")
    print(numbers)

    print("Enter a value: ")
    key = int(input())
    print("\n")

    # This takes around O(n log n)
    numbers.sort()

    # This takes O(log n)
    keyIndex = binary_search(numbers, key)

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


if __name__ == "__main__":
    main()