二分查找

二分法

二分法是一种快速查找的方法，时间复杂度低，逻辑简单易懂，总的来说就是不断的除以2除以2...
例如需要查找有序list里面的某个关键字key的位置，那么首先确认list的中位数mid，下面分为三种情况：
如果 list[mid] < key,说明key 在中位数的 右边；
如果 list[mid] > key,说明key 在中位数的 左边；
如果 list[mid] = key,说明key 在中位数的中间；
范围每次缩小一半，写个while的死循环知道找到为止。

二分法查找非常快且非常常用，但是唯一要求是要求数组是有序的

• 猜数字

def binary_aearch(list, num):
    """
    接受有序数组和一个元素，返回这个元素的位置
    """
    lef = 0
    right = len(list) - 1  # 获取列表最后一位数据
    print('左边界{}右边界{}'.format(lef,right) )
    while lef <= right:
        mid = (lef + right) // 2   # 如果（lef + right）不是偶数，python会自动向下取整
        guess = list[int(mid)]   
        if guess == num:     # 找到了元素
            return mid
        elif guess > num:    # 预期结果大于实际结果
            right = mid - 1
        elif guess < num:    # 预期结果小鱼实际结果
            lef = mid + 1
    return None

def 



if __name__ == "__main__":

    my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    print(binary_aearch(my_list, 7))

• 计算次方根

原理：原理为一个数的平方根一定在，0到这个数之间，那么就对这之间的数，进行二分遍历

def get_square(num):
    """
    num : 输入的数据
    return : 返回数据次方根
    """
    lef = 0
    right = int(num)
    print('左边界{}右边界{}'.format(lef,right) )
    while lef <= right:
        mid = (lef + right) // 2   # 如果（lef + right）不是偶数，python会自动向下取整
        if  num == 2 ** mid :   
             return mid
        elif 2**mid > num:
              right = mid - 1
        else:
              lef = mid + 1
    return None