""" 
@project: books
@file: binary_search.py 
@time: 2021/08/11
@software: PyCharm
@author: zy7y
二分查找算法:
二分查找是一种算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要
查找的元素包含在列表中，二分查找返回其位置；否则返回null

猜大小游戏
给定 1 ~ 100 中的某个数字 55
非二分查找： 从 1 依次 向上猜到 55 共计猜55次
二分查找：从50开始猜， 次数就会少很多(每次猜中间的数字)，共计 7次
50 -> 小了
75 -> 大了
63 -> 大了
56 -> 大了
53 -> 小了
54 -> 小了
55 -> 对了

对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步。
即 8个元素的列表， 使用二分查找需要 log2 8 = 3


对数：
log10100相当于问“将多少个10相乘的结果为100”。答案是两个： 10 × 10 = 100。因此， log10100 = 2。

时间（大O）: O(logn)

二分查找的速度比简单查找快得多。
 O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。
 算法运行时间并不以秒为单位。
 算法运行时间是从其增速的角度度量的。
 算法运行时间用大O表示法表示。
"""
from typing import List, Union


def binary_search(arr: List[int], item) -> Union[int, None]:
    """
    二分查找，传入一个有序序列，和序列中某个元素值，快速找到其下标
    :param arr: 有序列表
    :param item: 查找元素值
    :return: 找到返回下标，找不到返回None
    """
    low = 0    # 起点
    high = len(arr) - 1  # 终点
    while low <= high:  # 起点小于终点 循环
        mid = (low + high) // 2  # 中间值
        guess = arr[mid]   # 取到中间值(下标)对应的value
        if guess == item:
            return mid      # 相等 return 下标
        if guess > item:
            high = mid - 1  # 值大，把终点调整为 中间值 - 1
        else:
            low = mid + 1   # 值小， 把起点调整为 中间值 + 1
    return None

my_list = [i
           for i in range(1000)
           if i % 2 == 1
           ]
print(binary_search(my_list, 55555555)) # => 1