12内置函数补充，递归以及二分法。

1、内置函数补充

　　1、lambda 匿名函数

　　　　lambda 参数：返回值

　　　　函数名称统一叫lambda--这就是为什么叫匿名函数的原因

　　2、sorted() 排序函数

　　　　sorted(iterable, key, reverse)

　　　　key:排序规则

　　　　运行流程:把可迭代对象中每一个元素交给后面的key函数来执行，可到一个数字(权重),通过这个数字来进行排序

　　3、filter() 过滤函数

　　　　filter(function, iterable)

　　　　把可迭代对象中的每一个元素交给前面的函数进行筛选，函数返回True或者False

　　4、map() 映射函数

　　　　map(function, itetable)

　　　　把可迭代对象中的数据交给前面的函数进行执行，返回值就是map的处理结果

2、递归

　　函数自己调用自己

　　最大深度: python写的1000--可以自己去改(import sys sys.getrecursionlimit())

　　原则：能用循环解决的问题，就不要用递归。

　　例子：　　

# 遍历文件夹，打印所有文件和普通文件的文件名
import os
def fun(filepath, n):
    #  1、拿到这个文件夹
    files = os.listdir(filepath)
    #  2、拿到每一个文件名
    for file in files:  # 文件名
        #  3、获取到路径
        f_d = os.path.join(filepath, file)
        #  4、判断是否是文件夹
        if os.path.isdir(f_d):
            #  5、如果是文件夹，再来一遍
            print("	"*n, file, ":")  # 打印文件名
            fun(f_d, n+1)
        else:
            print("	"*n, file)  # 打印文件名

3、二分法(与之对应的还有三分法)

　　核心：掐头去尾取中间,一次砍一半。

　　两种算法:常规循环，递归循环

# 使用二分法可以提高效率，前提条件：有序序列。
lst = [22, 33, 44, 55, 66, 77, 88, 222, 444, 555, 777, 888, 999]
n = 88

left = 0
right = len(lst) - 1

while left < right:  # 边界,当右边比左边还小的时候退出循环(这里比较的是索引。当左边界不小于右边界，代表已经重合，即比较完毕)
    mid = (left + right) // 2  # 必须是整除,索引没有小数
    if lst[mid] > n:
        right = mid - 1
    if lst[mid] < n:
        left = mid + 1
    if lst[mid] == n:
        print("找到了这个数")
        break
else:
    print("没有找到这个数")


# 自定义一个list，用递归来完成二分法,要求如果找到，返回对应的索引，没找到返回-1。
lst = [22, 33, 44, 55, 66, 77, 88, 222, 444, 555, 777, 888, 999]


def fun(n, left, right):
    if left < right:
        mid = (left+right)//2
        if n > lst[mid]:
            left = mid + 1
            # 深坑。函数的返回值返回给调用者。如循环多次，最外层拿不到最里面一层的返回值，故每一次递归都要return
            return fun(n, left, right)
        if n < lst[mid]:
            right = mid - 1
            return fun(n, left, right)
        if n == lst[mid]:
            print('找到了')
            return mid
    else:
        print("没有这个数")
        return -1


fet = fun(66, 0, len(lst)-1)
print(fet)

# 重复查询的最优查询

lst = [6, 5, 7, 8]
lst2 = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]     # 准备一个足够多数据的数组(长度大于需要查询的数据的最大值)
for i in lst:    # 对需要查数据的列表的每一项的值进行遍历(注意不是遍历索引)
    lst2[i] = 1  # 在lst中查到的值换成lst2中对应的索引，修改为1。
print(lst2)
# 随后只需要判断lst2的索引是否为1即可。