Python【day 14-3】二分法查找

 1 #二分法查找
 2 #方法1 循环+左右边界变动,两者差减半
 3 #方法2 递归+新列表长度减半
 4 #方法3 递归+左右边界变动,两者差减半
 5 
 6 #方法1 循环+左右边界变动,两者差减半
 7 def recursion1(n1,li1):  #1 简洁  推荐
 8     left = 0
 9     right = len(li1)-1
10     while left <= right:
11         mid = (left + right) // 2
12         if n1 < li1[mid]:
13             right = mid -1
14         elif n1 > li1[mid]:
15             left = mid + 1
16         else:
17             print('%s 找到了' % n1)
18             break
19     else:
20         print('%s 没找到' % n1)
21         return False
22 n1 = 3
23 li1 = [1,2,3,4,5]
24 recursion1(n1,li1)
25 print('--------------------1 二分法 循环-左右边界变动,两者差减半')
26 
27 #方法2 递归+新列表长度减半
28 def recursion2(n2,li2):
29     left = 0
30     right = len(li2)-1
31     if left <= right:
32         mid = (left + right) // 2
33         if n2 < li2[mid]:
34             li3 = li2[:mid-1]
35         elif n2 > li2[mid]:
36             li3 = li2[mid+1:]
37         else:
38             print('%s 找到了' % n2)
39             return True
40         return recursion2(n2,li3)
41     else:
42         print('%s 没找到' % n2)
43         return False
44 n2 = 4
45 li2 = [1,2,3,4,5]
46 recursion2(n2,li2)
47 print('--------------------2 二分法 递归-新列表长度减半')
48 
49 #方法3 递归+左右边界变动,两者差减半
50 def recursion3(n3,li3,left,right):
51     if left <= right:
52         mid = (left + right) // 2
53         if n3 > li3[mid]:
54             left = mid + 1
55         elif n3 < li3[mid]:
56             right = mid - 1
57         else:
58             print('%s 找到了' % n3)
59             return True
60         return recursion3(n3,li3,left,right)
61     else:
62         print('%s 没找到' % n3)
63         return False
64 n3 = 5
65 li3 = [1,2,3,4,5]
66 left = 0
67 right = len(li3)-1
68 recursion3(n3,li3,left,right)
69 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)  #5
print('----------------------3 二分法查找--递归写法1--产生新列表1')



 1 ''''''
 2 '''
 3 二分法查找,递归方法1,伪代码思路
 4 1、每次递归调用会新产生一个新的列表(是原来列表长度的一半)
 5 2、先定义左右边界的索引号-下标,以及中位数的索引号-下标
 6 
 7 条件是left<=right  #注意:必须加上等于
 8 3、当目标数大于中位数的时候,新的列表切片li2 = li1[mid+1:]
 9     递归调用自己
10 4、当目标数小于中位数的时候,新的列表切片li2 = li1[:mid]
11     递归调用自己
12 5、当目标数等于中位数的时候,找到了
13 
14 如果left<right
15 6、上述3,4,5都执行完毕,没有找到的话,返回-找不到
16 
17 注意点:
18 1、递归的入口前面需要return
19     原因:实现第5次递归调用的返回值,会依次传递给第1次递归调用
20 2、二分法的适用场景
21     列表必须是已经排序后的
22 
23 缺点:
24 变动的是列表,每次产生一个新列表(元素是之前列表的一半)
25 1、得不到目标数的索引号-下标-位置
26     因为每次都切了一半,产生了一个新的列表
27 2、比较浪费内存空间
28     因为每次递归调用,都会产生一个新的列表
29     比如:1亿元素的列表,第1次递归调用,就新产生了一个5000万的列表
30                        第2次递归调用,就新产生了一个2500万的列表。。。依次类推
31 '''
32 
33 
34 def recursion1(n,li):
35     left = 0  #1 定义左边界的索引号-下标-位置
36     # right = len(li1)-1
37     right = len(li)-1  #注意3:拼写错误,是li而不是li1
38     #2 定义右边界的索引号-下标-位置
39 
40     if left<=right: #3 左边界位置小于等于右边界的位置
41         #注意4:需要包含等于=
42         # middle = (right - left) // 2  # 整除 中位数的索引号-下标
43         middle = (right + left) // 2  #5 注意1: 求中位数 是+ 而不是 -
44         if n>li[middle]: #6 如果目标数大于中位数
45             li2 = li[middle+1:]  # 9 新产生一个新列表,长度是之前的一半(左边界变了)
46             # 注意4: +和:的优先级 #冒号的优先级高于+
47             return recursion1(n,li2)  #10 参数1是目标数不变,参数2是新列表(变了)
48             # 注意5: 递归调用自己 前面加return  递归入口
49         elif n<li[middle]: #7 如果目标数小于中位数
50             # li3 = li[:middle]  #
51             li2 = li[:middle]  #11 新产生一个新列表,长度是之前的一半(右边界变了)
52             # 注意2:这里是li2 而不能是li3 必须是同一个列表才对(和上面的分支)
53             return recursion1(n,li2)  # 12 参数1是目标数不变,参数2是新列表(变了)
54         else: #8 如果目标数等于中位数
55             print('%s 找到了' % n)
56             return True  #13 找到了 返回True
57     else:  #4 如果左边界位置大于右边界的位置
58         print('%s 找不到' % n)
59         return False #14 找不到 返回False
60 
61 li1 = [1,2,3,4,5,6]
62 n = 7
63 ret1 = recursion1(n,li1) #参数1是目标数,参数2是列表(查找范围)
64 if ret1:
65     print('%s 找到了-' % n)
66 else:
67     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-每次递归,左右边界位置都会变化,两者之差减半
'''


  

 

https://www.cnblogs.com/wangtp/p/11797137.html

Python量化投资网携手4326手游为资深游戏玩家推荐:《【王牌御史】5月17日版本更新情报来袭

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论