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

发布时间：2018-04-08 21:34:09编辑：Run阅读（3983）

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)

执行结果



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




可以更改递归深度


例

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

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






例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




二分查找法(算法)






如果有这样一个列表，让你从这个列表中找到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,其它不变









最终代码

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

关键字：