查找算法

"""
查找
判断一个算法好坏的标准：渐近时间复杂度和渐近空间复杂度
时间和空间通常是不可调和的矛盾
所以在设计算法时要考虑用空间换时间(*)还是时间换空间
描述算法的渐近时间复杂度一般使用O标记
例如二重循环里外都是N的循环那么就记为O(N**2)
"""


def seq_search(items, key):
    """顺序查找 - 线性时间复杂度 - O(N)"""
    for index, item in enumerate(items):
        if item == key:
            return index
    return -1


def bin_search(items, key):
    """折半查找（二分查找） - 对数时间复杂度 - O(log_2N)"""
    start, end = 0, len(items) - 1
    while start <= end:
        mid = (start + end) // 2
        if key < items[mid]:
            end = mid - 1
        elif key > items[mid]:
            start = mid + 1
        else:
            return mid
    return -1


def main():
    """主函数"""
    items = [12, 25, 33, 57, 69, 98]
    print(bin_search(items, 35))
    print(bin_search(items, 12))
    print(bin_search(items, 69))
    print(bin_search(items, 98))


if __name__ == '__main__':
    main()