#二分法查找

 #方法1 循环+左右边界变动，两者差减半

 #方法2 递归+新列表长度减半

 #方法3 递归+左右边界变动，两者差减半

 #方法1 循环+左右边界变动，两者差减半

 def recursion1(n1,li1):  #1 简洁  推荐

     left = 0

     right = len(li1)-1

     while left <= right:

         mid = (left + right) // 2

         if n1 < li1[mid]:

             right = mid -1

         elif n1 > li1[mid]:

             left = mid + 1

         else:

             print('%s 找到了' % n1)

             break

     else:

         print('%s 没找到' % n1)

         return False

 n1 = 3

 li1 = [1,2,3,4,5]

 recursion1(n1,li1)

 print('--------------------1 二分法 循环-左右边界变动，两者差减半')

 #方法2 递归+新列表长度减半

 def recursion2(n2,li2):

     left = 0

     right = len(li2)-1

     if left <= right:

         mid = (left + right) // 2

         if n2 < li2[mid]:

             li3 = li2[:mid-1]

         elif n2 > li2[mid]:

             li3 = li2[mid+1:]

         else:

             print('%s 找到了' % n2)

             return True

         return recursion2(n2,li3)

     else:

         print('%s 没找到' % n2)

         return False

 n2 = 4

 li2 = [1,2,3,4,5]

 recursion2(n2,li2)

 print('--------------------2 二分法 递归-新列表长度减半')

 #方法3 递归+左右边界变动，两者差减半

 def recursion3(n3,li3,left,right):

     if left <= right:

         mid = (left + right) // 2

         if n3 > li3[mid]:

             left = mid + 1

         elif n3 < li3[mid]:

             right = mid - 1

         else:

             print('%s 找到了' % n3)

             return True

         return recursion3(n3,li3,left,right)

     else:

         print('%s 没找到' % n3)

         return False

 n3 = 5

 li3 = [1,2,3,4,5]

 left = 0

 right = len(li3)-1

 recursion3(n3,li3,left,right)

 print('--------------------3 二分法 递归-左右边界变动，两者差减半')

#需求 如何判断数字3是否在列表中

#方法1 遍历循环列表

li1 = [1,2,3,4]

for i in li1:

    if i==3:

        print('3在列表中')

        break

else: #如果for循环正常结束，如果有break就不会执行整个else

    print('3不在列表中')

#这个时间复杂度是O（n），这个n是列表的长度，即时间复杂度和列表的长度呈正比

#列表的长度是多少，就需要比较多少次

print('----------------------1 遍历循环')

#方法2 二分法查找--常规写法--条件循环while

'''

二分法查找算法

优点：效率非常高

    1、比如：1亿个元素的列表，循环遍历，需要比较1亿次

    2、如果是二分法，需要比较2的27次方大约是1.3亿，即只需要比较27次即可（比较次数相差近400万倍）

        二分法的对比范围从64-32-16-8-4-2-1 每次比较，都会将对比范围缩小一半

缺点：必须是有序序列，先要排序--sorted

二分法伪代码思路

前提：列表已经做了排序-从小到大

1、获取中位数的索引号-下标

2、拿目标数和列表的中位数进行比较

    1、如果比中位数小，就在中位数的左边，右边界索引号变成了中位数索引号-下标减1

    2、如果比中位数大，就在中位数的右边，左边界索引号变成了中位数索引号-下标加1

3、上述循环退出的条件是

    1、找到了break，打印出其索引号-下标

    2、没有找到，循环正常结束，提示-没有找到-else

    3、当左边界的索引号>=右边界的缩影好-下标（条件循环，用while）

'''

li1 = [0,1,2,3,4,5,6,7,8,9]

left = 0  #初始左边界的索引号-下标

right = len(li1)-1   #初始右边界的索引号-下标

n=3  #定义要找的目标数

while left<=right: #条件循环，条件是左边界小于等于右边界的下标（如果左边界大于右边界的下标，就停止循环了）

# while left<right: #条件循环，条件是左边界小于等于右边界的下标（如果左边界大于右边界的下标，就停止循环了）

    #注意:这里是小于等于，而不是小于；小于会漏掉一种情况(就是left和right都是3，相等-循环结束了，

    #实际上，left和right相等就是找到了，索引号就是3，而不应该跳出循环) 这个是边界值

    # 小结：大概思路是对的，但是结果验证是不对的，就需要微调边界值了

    middle = (left + right) // 2  # 中位数的索引号-下标

    # 用整除//而不是除号/的原因是：索引号是整数，不能是小数

    # print(middle)

    #随着left和right的不断改变，middle的值也在随之改变

    if n<li1[middle]:  #1如果目标数小于中位数

        right = (middle-1) #2右边界的索引号-下标变成了中位数的下标-1

        # print(right)  #3

    elif n>li1[middle]: #3如果目标数大于中位数

        left = (middle + 1) #4左边界的索引号-下标变成了中位数的下标+1

        # print(left)  #3

    else: #5 如果目标数和中位数相等

        print('找到了，该数在列表中的索引号-下标是 %s' % middle) #6 打印-找到了，目标数的下标

        break #7 跳出整个循环

else: #8 当循环正常结束，即没有break的时候，提示没有找到

    print('%s 在列表中没有找到' % n)

print('----------------------2 二分法查找--常规写法--条件循环while')

'''

排错小结：

while中left和right的条件判断，是小于等于，而不是小于；

小于会漏掉一种情况(就是left和right都是3，相等-循环结束了，

实际上，left和right相等就是找到了，索引号就是3，而不应该跳出循环

这个等于是边界值（临界值）

归纳：大体思路是对的，但是结果验证是不对的，就需要微调边界值了

    根据反馈，调试程序就是在刻意练习重复的过程

二分法中，如果列表的有多个相同的元素，那么目标数的索引号不一定是最左边的那个元素的索引号

（这个和循环遍历列表不同，循环遍历的话，返回的索引号就是最左边的）

li1 = [1,2,2,2,2,4,4,4,4,5]

'''

#方法3 二分法查找--递归写法1

'''

方法论小结：

1、当遇到不好理解的地方，怎么办？

    1、放慢（一倍或者一倍以上）速度，反复听几次，反复练习几次

    2、听的时候，多暂停，多停下来思考，想明白了，再继续

       当思考速度慢于接收速度太多的时候，一定要暂停，

       让思考跟上接收的速度

2、递归的返回

    1、比如一共是5次递归，那么第5次递归的返回值，会给到第4次调用

        但是函数最后的返回值，是第2次递归的返回值，会给到第1次调用

        也就是说，函数最后的返回值是第2次递归的返回值，而不是第5次递归的返回值

        （第5次递归的返回值和第2次递归的返回值，是不一样的）

    2、如何让第5次递归的返回值和第2次递归的返回值一样呢

       答案是：让第5次递归的返回值先给到第4次调用，然后给到第3次调用

               接着给到第2次调用，最后给到第一次调用，连续传递

               语法是：在递归的入口前面加上return即可

3、方法3的缺点

    方法3变动的是列表，每次产生一个新列表（元素是之前列表的一半）

    1、得不到目标数的索引号-下标-位置

        因为每次都切了一半，产生了一个新的列表

    2、比较浪费内存空间

        因为每次递归调用，都会产生一个新的列表

        比如：1亿元素的列表，第一次递归调用，就新产生了一个5000万的列表

                           第2次递归调用，就新产生了一个2500万的列表.。。依次类推

4、方法4

    列表不变（不新产生列表），变动的是左右边界的索引号-下标-位置

'''

def func3():

    len('hello')

ret1 = func3()

print(ret1)  #None

def func4():

    return len('hello')

    #要得到长度5，在len('hello# ')前面加上return即可

    #同理，递归的入口也是一样 要想让第3次递归调用返回值给到第1次调用

    # 过程是：第3次递归调用返回值给到第2次调用，第2次调用返回值再给到第1次调用

    #即 在递归调用的入口前 加上return，从而实现连续传递返回值

ret2 = func4()

print(ret2)  #

print('----------------------3 二分法查找--递归写法1--产生新列表1')

 ''''''

 '''

 二分法查找，递归方法1，伪代码思路

 1、每次递归调用会新产生一个新的列表（是原来列表长度的一半）

 2、先定义左右边界的索引号-下标，以及中位数的索引号-下标

 条件是left<=right  #注意：必须加上等于

 3、当目标数大于中位数的时候,新的列表切片li2 = li1[mid+1:]

     递归调用自己

 4、当目标数小于中位数的时候,新的列表切片li2 = li1[:mid]

     递归调用自己

 5、当目标数等于中位数的时候,找到了

 如果left<right

 6、上述3,4，5都执行完毕，没有找到的话，返回-找不到

 注意点：

 1、递归的入口前面需要return

     原因：实现第5次递归调用的返回值，会依次传递给第1次递归调用

 2、二分法的适用场景

     列表必须是已经排序后的

 缺点：

 变动的是列表，每次产生一个新列表（元素是之前列表的一半）

 1、得不到目标数的索引号-下标-位置

     因为每次都切了一半，产生了一个新的列表

 2、比较浪费内存空间

     因为每次递归调用，都会产生一个新的列表

     比如：1亿元素的列表，第1次递归调用，就新产生了一个5000万的列表

                        第2次递归调用，就新产生了一个2500万的列表。。。依次类推

 '''

 def recursion1(n,li):

     left = 0  #1 定义左边界的索引号-下标-位置

     # right = len(li1)-1

     right = len(li)-1  #注意3：拼写错误，是li而不是li1

     #2 定义右边界的索引号-下标-位置

     if left<=right: #3 左边界位置小于等于右边界的位置

         #注意4：需要包含等于=

         # middle = (right - left) // 2  # 整除 中位数的索引号-下标

         middle = (right + left) // 2  #5 注意1： 求中位数 是+ 而不是 -

         if n>li[middle]: #6 如果目标数大于中位数

             li2 = li[middle+1:]  # 9 新产生一个新列表，长度是之前的一半（左边界变了）

             # 注意4： +和:的优先级 #冒号的优先级高于+

             return recursion1(n,li2)  #10 参数1是目标数不变，参数2是新列表（变了）

             # 注意5： 递归调用自己 前面加return  递归入口

         elif n<li[middle]: #7 如果目标数小于中位数

             # li3 = li[:middle]  #

             li2 = li[:middle]  #11 新产生一个新列表，长度是之前的一半（右边界变了）

             # 注意2：这里是li2 而不能是li3 必须是同一个列表才对（和上面的分支）

             return recursion1(n,li2)  # 12 参数1是目标数不变，参数2是新列表（变了）

         else: #8 如果目标数等于中位数

             print('%s 找到了' % n)

             return True  #13 找到了 返回True

     else:  #4 如果左边界位置大于右边界的位置

         print('%s 找不到' % n)

         return False #14 找不到 返回False

 li1 = [1,2,3,4,5,6]

 n = 7

 ret1 = recursion1(n,li1) #参数1是目标数，参数2是列表（查找范围）

 if ret1:

     print('%s 找到了-' % n)

 else:

     print('%s 找不到-' % n)

''''''

'''

二分法查找-递归方法2-伪代码思路

1、递归方法1是每次递归调用，都新产生一个新的列表（长度减半）

2、递归方法1是每次递归调用，列表不变（不产生新的列表）

   变动的是列表的左右边界-位置（每次递归调用，右边界和左边界下标的差就减少一半）

   直到最后左右边界重合（找到了）

1、函数参数是4个

    参数1：目标数

    参数2：查找范围-列表

    参数3：左边界位置-下标

    参数4：右边界位置-下标

2、定义中位数

3、判断条件：左边界小于等于右边界   注意：等于不能遗漏

4、判断目标数和中位数的大小

    1、目标数大于中位数

        左边界变动到中位数位置+1

    2、目标数小于中位数

        右边界变动到中位数位置-1

    3、目标数等于中位数

        找到了，返回True

    4、递归调用自己（参数：目标数、列表、左边界、右边界）

        每次递归，左右边界都变动了

        右边界和左边界下标的差每次递归减少一半

5、如果左边界大于右边界

    没有找到，返回False

'''

def recursion2(n,li2,left,right):

    #参数1：目标数

    #参数2：查找范围-列表

    #参数3：左边界位置

    #参数4：右边界位置

    if left <= right:  #1 左边界位置小于等于右边界位置  #注意1：等于 不能遗漏

        mid = (left + right) // 2 # 2 取中位数的位置 #注意2：用整除，而不是除号 位置是整数

        if n < li2[mid]: #5 如果目标数小于中位数

            right = mid - 1 #右边界位置改变到中位数位置-1

        elif n > li2[mid]: #6 如果目标数大于中位数

            left = mid + 1  #左边界位置改变到中位数+1

        else: #7 如果目标数等于中位数

            print('%s 找到了' % n)  #找到了，返回True

            return True

        return recursion2(n,li2,left,right) #递归入口，每次递归调用，左右边界的位置都变了

        #注意点3：前面必须加上return，才会实现第5次递归调用的返回值，依次传到了第一次递归调用

                 #如果没有加上return，第5次递归调用的返回值会给到第4次递归调用，而不会依次传递到第一次递归调用

                 #函数最后返回值取的是第一次递归调用

    else:  #3 如果左边界大于右边界

        print('%s 没有找到' % n) #4 没有找到，目标数不在列表-查找范围中

        return False

n=4

li2 = [1,2,3,4,5,6]

left = 0 #定义左边界的初始值

right = len(li2) -1  #定义右边界的初始值

recursion2(n,li2,left,right)

print('--------------------------1 递归方法2 改变左右边界的位置')

# def recursion3(n,li2,left=0,right=-1):

def recursion3(n,li2,left=0,right=len(li2)-1):

    # if right == -1:  #条件判断，如果右边界取默认值-1

    #     #注意点4：这么做的原因是，形参列表写入right=len(li2)-1可能不行，当然这里是可以的

    #             如果形参列表不允许直接写类似len(li2)-1 就可以用这个方式，一个新的思路

    #     right = len(li2)-1 #就把右边界置为初始值 len(li2)-1

    #参数1：目标数

    #参数2：查找范围-列表

    #参数3：左边界位置  用的是默认参数 左边界初始值是0

    #参数4：右边界位置  用的是默认参数 右边界初始值设置成-1 然后修改

    if left <= right:  #1 左边界位置小于等于右边界位置  #注意1：等于 不能遗漏

        mid = (left + right) // 2 # 2 取中位数的位置 #注意2：用整除，而不是除号 位置是整数

        if n < li2[mid]: #5 如果目标数小于中位数

            right = mid - 1 #右边界位置改变到中位数位置-1

        elif n > li2[mid]: #6 如果目标数大于中位数

            left = mid + 1  #左边界位置改变到中位数+1

        else: #7 如果目标数等于中位数

            print('%s 找到了' % n)  #找到了，返回True

            return True

        return recursion2(n,li2,left,right) #递归入口，每次递归调用，左右边界的位置都变了

        #注意点3：前面必须加上return，才会实现第5次递归调用的返回值，依次传到了第一次递归调用

                 #如果没有加上return，第5次递归调用的返回值会给到第4次递归调用，而不会依次传递到第一次递归调用

                 #函数最后返回值取的是第一次递归调用

    else:  #3 如果左边界大于右边界

        print('%s 没有找到' % n) #4 没有找到，目标数不在列表-查找范围中

        return False

n=5

li2 = [1,2,3,4,5,6]

# left = 0 #定义左边界的初始值

# right = len(li2) -1  #定义右边界的初始值

recursion3(n,li2,left,right)

print('--------------------------2 默认参数1 递归方法2 改变左右边界的位置')

def recursion4(n,li2,left=0,right=-1):

# def recursion4(n,li2,left=0,right=len(li2)-1):

    if right == -1:  #条件判断，如果右边界取默认值-1

        #注意点4：这么做的原因是，形参列表写入right=len(li2)-1可能不行，当然这里是可以的

                # 如果形参列表不允许直接写类似len(li2)-1 就可以用这个方式，一个新的思路

        right = len(li2)-1 #就把右边界置为初始值 len(li2)-1

    #参数1：目标数

    #参数2：查找范围-列表

    #参数3：左边界位置  用的是默认参数 左边界初始值是0

    #参数4：右边界位置  用的是默认参数 右边界初始值设置成-1 然后修改

    if left <= right:  #1 左边界位置小于等于右边界位置  #注意1：等于 不能遗漏

        mid = (left + right) // 2 # 2 取中位数的位置 #注意2：用整除，而不是除号 位置是整数

        if n < li2[mid]: #5 如果目标数小于中位数

            right = mid - 1 #右边界位置改变到中位数位置-1

        elif n > li2[mid]: #6 如果目标数大于中位数

            left = mid + 1  #左边界位置改变到中位数+1

        else: #7 如果目标数等于中位数

            print('%s 找到了' % n)  #找到了，返回True

            return True

        return recursion2(n,li2,left,right) #递归入口，每次递归调用，左右边界的位置都变了

        #注意点3：前面必须加上return，才会实现第5次递归调用的返回值，依次传到了第一次递归调用

                 #如果没有加上return，第5次递归调用的返回值会给到第4次递归调用，而不会依次传递到第一次递归调用

                 #函数最后返回值取的是第一次递归调用

    else:  #3 如果左边界大于右边界

        print('%s 没有找到' % n) #4 没有找到，目标数不在列表-查找范围中

        return False

n=6

li2 = [1,2,3,4,5,6]

# left = 0 #定义左边界的初始值

# right = len(li2) -1  #定义右边界的初始值

recursion4(n,li2,left,right)

print('--------------------------3 默认参数2 递归方法2 改变左右边界的位置')

'''

二分法查找小结

方法1：循环--每次循环，左右边界位置都会变化，两者之差减半

方法2：递归1-每次递归都产生一个新列表，长度是之前列表减半

方法3：递归2-每次递归，左右边界位置都会变化，两者之差减半

'''