首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >python3--递归函数,二分查找算法的实现

python3--递归函数,二分查找算法的实现

作者头像
py3study
发布2018-08-02 16:40:33
7750
发布2018-08-02 16:40:33
举报
文章被收录于专栏:python3python3

enumerate枚举的用法

例子1

li = ['Sam', 'Tom', 'Jack', '老王']
for index, name in enumerate(li):  # 用两个变量接收,一个接收索引值,一个接收列表里的每个元素
    print(index, name)

执行结果

0 Sam

1 Tom

2 Jack

3 老王

例子2

li = ['Sam', 'Tom', 'Jack', '老王']
for index, name in enumerate(li, 100):  # 设置起始值为100
    print(index, name)

执行结果

100 Sam

101 Tom

102 Jack

103 老王

map会根据提供的函数对指定序列做映射

例1

# lambda匿名函数 x为后面列表里的每个元素,冒号后面则是返回值,字符串拼接x+'_sb',最后生成一个迭代器
ret = map(lambda x: x+'_sb', ['Tom', '老王', 'Jack'])  
for i in ret:
    print(i)

执行结果

Tom_sb

老王_sb

Jack_sb

例2

ret1 = map(lambda x: x if x > 4 else x**2,[1,2,3,4,5,6,7])
for i in ret1:
    print(i)

执行结果

1

4

9

16

5

6

7

列表推导式

l1 = [i**2 for i in [1,2,3,4,5,6]]  # for前面的i**2为返回值,i是列表中的每个元素
print(l1)

执行结果

[1, 4, 9, 16, 25, 36]

filter过滤

例1

ret = filter(lambda x: x%2 == 0, [1,2,3,4,5,6,7])  
# lambda x:x%2 == 0,lambda使用匿名函数,x为后面列表的每个元素,x%2==0 条件对2取余等于0
# filter过滤掉不符合的元素,留下符合条件的元素,最后生成一个迭代器
for i in ret:
    print(i)

执行结果

2

4

6

例2

ret = filter(lambda x: x>4, [1,2,3,4,5,6,7])
#取x大于4的元素,把不符合的过滤掉,生成一个迭代器
for i in ret:
    print(i)

执行结果

5

6

7

max求最大值

# key = lambda 自定义条件,x:len(x)返回列表中长度最大的一个 
print(max([[1,2,3],[4,5,6,7],[11,],[3,3,3,3,3,3,3,3]],key=lambda x:len(x)))

执行结果

[3, 3, 3, 3, 3, 3, 3, 3]

递归函数

普通程序员理解函数,高级程序员理解递归(差距很明显~~)

递归函数,在一个函数里执行调用这个函数本身,递归的最大深度998

举例:

# 这是一个死循环程序,函数执行打印666,执行完毕,释放内存,然后继续执行函数打印666,在释放内存,反反复复
def func1():
    print(666)

while True:
    func1()

在来看递归的实现

# 执行funcl,打印666,在内部继续执行func1,打印666,
# 也就是这个函数一直循环执行,不会结束。一直打开内存,并不会释放
def func1():
    print(666)
    func1()
func1()

传参方式

def func1(n):
    n += 1
    print(n) #也可以打印内存地址 print(id(n)),可以看到每次内存地址不一样,即每次都开辟一个新的内存空间
    func1(n)
func1(0)

执行结果

blob.png
blob.png

递归,执行一次开辟一个空间,python对内存有个保护机制,默认只能递归到998层

可以更改递归深度

import sys
sys.setrecursionlimit(10000)
def func1(n):
    n += 1
    print(n)
    func1(n)
func1(0)

执行结果,windows系统一般都差不多3809层,mac,linux会达到几万以上,这是系统性能问题。

blob.png
blob.png

例2

def age(n):
    if n == 1:
        return 18
    else:
        return age(n - 1) + 2
print(age(4))

# 注释 第一步执行age(4)函数,并传入一个参数4
# 第二步传参n=4,走else,此时age(4-1) + 2
# 第三步执行age(4-1)函数,n = 4-1,走else,此时age(4-1-1) + 2 +2
# 第四步执行age(4-1-1)函数,n = 4-1-1,走else,此时age(4-1-1-1) + 2 +2 +2
# 第五步执行age(4-1-1-1)函数,n = 4-1-1-1,走if,此时返回18给调用者
# 也就是age(4-1-1-1) = 18,加上之前的 +2 +2 +2,最终结果18+2+2+2=24

执行结果

24

二分查找法(算法)

blob.png
blob.png

如果有这样一个列表,让你从这个列表中找到66的索引位置,你要怎么做?

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

第一种方法

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
print(l.index(66))

执行结果

17

第二种方法

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
count = 0
for i in l:
    if i == 66:
        print(count)
        break
    count += 1

执行结果

17

如果列表很大,上面那两种方法查找就会慢很多,它的执行顺序是从前往后,如果要找的数在最后面,就需要把列表全部遍历一遍

第三种:二分查找(每次从中间取值,比较大小,如果要找的数字比中间值大(如果比中间值小,就取前面那一半),就直接找中间值后面的那一半,继续对半切片查找,在比较,直到找到为止)

二分查找条件(有序且唯一的数字数列)

错误方法示例

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
def two_search(li,aim): #二分查找,li表示列表,aim是目标数,比如要找10
    mid_index = len(li) //2 #取列表中间的索引
    if li[mid_index] < aim: #判断列表中间的数小于目标数
        return two_search(li[mid_index+1:],aim) #因为已经判断中间的数了,需要加1。切片
    elif li[mid_index] > aim:
        return two_search(li[:mid_index:], aim) #这里不用减,因为它取不到中间数,也就是末尾的数
    elif li[mid_index] == aim:
        return mid_index
    else:
        return '没有此值'

ret = two_search(l,55)
print(ret)

执行结果

0

原因:每次进行切片操作时(都形成了一个新的列表)索引值发生了改变,导致最终结果不对。

所以为了解决这个问题,列表不能变,必须要用原来的列表,索引不能变,不能用切片,需要改变中间值,也就是mid_index,其它不变

blob.png
blob.png

最终代码

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
def two_search(li, aim, start=0, end=None):
    end = len(li)-1 if end is None else end
    mid_index = (end - start) // 2 + start  # 3
    if start <= end:
        if li[mid_index] < aim:
            return two_search(li,aim,start=mid_index+1,end=end)
        elif li[mid_index] > aim:
            return two_search(li,aim,start=0,end=mid_index-1)
        elif li[mid_index] == aim:
            return mid_index
        else:
            return '没有此值'
    else:
        return '没有此值'

print(two_search(l,42))

执行结果

13

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-04-08 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档