# 一、二分法
for循环遍历查找 效率不高。
 使用二分法的大前提：`有序序列类型是从小到大排列`  list.sort()将列表升序
假设我找的那个值比中间那个值大，左侧就不用找了。
再从剩余的区域中间值比较，无限重复这个过程直到找到为止。二分法是递归一种运用
l=[1,2,10,30,33,99,101,200,301,402]
二分法start stop 区间查找。代码封装如下
def search(num,l,start=0,stop=len(l)-1):
    if start <= stop:
        mid=start+(stop-start)//2
        print('start:[%s] stop:[%s] mid:[%s] mid_val:[%s]' %(start,stop,mid,l[mid]))
        if num > l[mid]:
            start=mid+1
            # search(num, l, start, stop) 
        elif num < l[mid]:
            stop=mid-1
            # search(num, l, start, stop)
        else:
            print('find it',mid)
            return
        search(num,l,start,stop)
    else: #如果stop > start则意味着列表实际上已经全部切完，即切为空
        print('not exists')
        return

search(301,l,3,9)

一、二分法

• 使用二分法的大前提：有序序列类型是从小到大排列

算法之二分法:大前提值是按照从小打到排列

需求：有1个按照从小到大顺序排列的数字列表
需要从该数字列表中找到我们想要的那个一个数字
如何做更高效？

方案一：for循环遍历查找

for num in l:
    if num ==13:
        print("找到了")
        break

方案二：二分法

假设我找的那个值比中间那个值大，左侧就不用找了。
再从剩余的区域中间值比较，无限重复这个过程直到找到为止

# 要找的find_num =13
find_num = 13
mid_value = "先找到中间的值"

if find_num > mid_value:
    # 接下来的查找应该是在右半部分
    # 列表 = 列表切片右半部分
    # 本身的代码（列表）
    pass
elif find_num < mid_value:
    # 接下来的查找应该是在右半部分
    # 列表 = 列表切片左半部分
    # 本身的代码（列表）
    pass
else:
    print("找到了")

# ---------------------------
# 1.把代码先缩进在一个函数里
def binary_search():
    # 要找的find_num =13
    find_num = 13
    mid_value = "先找到中间的值"

    if find_num > mid_value:
    # 接下来的查找应该是在右半部分
    # 列表 = 列表切片右半部分
    # 本身的代码（列表）
        pass
    elif find_num < mid_value:
    # 接下来的查找应该是在右半部分
    # 列表 = 列表切片左半部分
    # 本身的代码（列表）
        pass
    else:
        print("找到了")
        
# 2. 优化代码:函数参数

def binary_search(find_num,list_num):
    """
    find_num: 要找的值
    list_num: 从哪里找
    """

    if len(list_num) ==0:
        print("没找到")
        return
    mid_index = len(list_num)//2
    mid_value = list_num[mid_index]

    if find_num > mid_value:
        list_num = list_num[mid_index + 1:]
        binary_search(find_num, list_num)
    elif find_num < mid_value:
        list_num = list_num[:mid_index]
        binary_search(find_num, list_num)
    else:
        print("找到了")

l = [1]
binary_search(3,l)      
        

二分法start stop 区间查找

image.png

l=[1,2,10,30,33,99,101,200,301,402]

def search(num,l,start=0,stop=len(l)-1):
    if start <= stop:
        mid=start+(stop-start)//2
        print('start:[%s] stop:[%s] mid:[%s] mid_val:[%s]' %(start,stop,mid,l[mid]))
        if num > l[mid]:
            start=mid+1
            # search(num, l, start, stop) 
        elif num < l[mid]:
            stop=mid-1
            # search(num, l, start, stop)
        else:
            print('find it',mid)
            return
        search(num,l,start,stop)
    else: #如果stop > start则意味着列表实际上已经全部切完，即切为空
        print('not exists')
        return

search(301,l,3,9)

案例： 二分法，找到了返回True没找到返回False

如果 用递归函数 我们要最终获取返回值return,需要注意的是：返回值 return 递归函数调用
原因是 你不知道什么时候递归结束。只有将下一次递归的返回值作为当前的返回值，最终才会得到最后一次递归的返回值，
 依次递推回来才会知道调用函数的返回值。
案例： 二分法，找到了返回True没找到返回False

def binary_search(find_num,list_num):
    """
    find_num: 要找的值
    list_num: 从哪里找
    """

    if len(list_num) ==0:
        print("没找到")
        return False
    mid_index = len(list_num)//2
    mid_value = list_num[mid_index]

    if find_num > mid_value:
        list_num = list_num[mid_index + 1:]
        return binary_search(find_num, list_num)
    elif find_num < mid_value:
        list_num = list_num[:mid_index]
        return binary_search(find_num, list_num)
    else:
        print("找到了")
        return True

l = [2,4,6,8,9,10,33,55,77,87,89,90,233]

print(binary_search(11,l))  # False
pass