"""
查找算法
    ~ 顺序查找：O(n)
    ~ 二分查找：O(log2 n)
"""


def seq_search(items, key):
    """
    顺序查找
    :param items: 被查找的列表
    :param key: 待查找的元素
    :return: 返回元素在列表中的位置或-1
    """
    for index, item in enumerate(items):
        if item == key:
            return index
    return -1


def bin_search(items, key):
    """
    二分查找（折半查找）
    :param items: 被查找的列表（有序）
    :param key: 待查找的元素
    :return: 待查找元素在列表的位置或-1
    """
    start, end = 0, len(items) - 1
    while start <= end:
        mid = (start + end) // 2
        if key > items[mid]:
            start = mid + 1
        elif key < items[mid]:
            end = mid - 1
        else:
            return mid
    return -1


def main():
    nums = [12, 34, 45, 58, 67, 69, 72, 81, 95, 99]
    print(bin_search(nums, 34))
    print(bin_search(nums, 12))
    print(bin_search(nums, 99))
    print(bin_search(nums, 72))
    print(bin_search(nums, 55))


if __name__ == '__main__':
    main()