1.图解算法（二分查找）

1.二分查找：适用于查找有序元素列表中的指定元素

特点：列表必须有序 对半拆分

问题：游戏 1-100中，小明设置一个数字，小红猜测，数字=小明设置正确，数字<小明设置 小明说小了 ，数字>小明设置 小明说大了，最多多少次小红能猜中数字？

使用折半法查找
第一步 100/2 =50 猜50

                        第二步   50/2    猜25

                        第三步   25/2    猜13

                        第四步    13/2  猜7

                         第五步    7/2    猜4

                         第6步     4/2     猜2

                         第7步    2/2     猜1

所以最多7步之内，肯定能得到答案

对于任意n个元素的有序序列，查找的步骤最多是

k即为最大次数

log是什么？ log是对数表达式，那对数是什么？ 对数运算是幂运算的逆运算

首先幂运算 比如 10*10=100 即

反过来 求x的值即为对数运算， 数学表达式为是

以下为二分查找python版代码表达式

# 循环
def brinary_search_(array, find):
    low = 0
    height = len(array) - 1
    while low <= height:
        mid = int((height + low) / 2)
        if array[mid] == find:  # 比较完中间值 后面无需再比较所以 mid的位置根据情况+1 or -1
            return mid
        if array[mid] > find:
            height = mid - 1
        else:
            low = mid + 1
    return -1


# 递归
def brinary_search(array, find, low, height):
    mid = int((height + low) / 2)
    if find > array[height] or find < array[low]:
        return -1
    if array[mid] == find:
        return mid
    if low > height:
        return -1
    if array[mid] > find:
        return brinary_search(array, find, low, mid - 1)
    if array[mid] < find:
        return brinary_search(array, find, mid + 1, height)


if __name__ == '__main__':
    myArray = [1, 3, 5, 7, 8, 10, 12]
    index = brinary_search_(myArray, 6)
    index_ = brinary_search(myArray, 8, 0, len(myArray) - 1)
    print(index)
    print(index_)