算法二分法
二分算法图
什么是算法？
算法是高效解决问题的办法。
需求：有一个按照从小到大顺序排列的数字列表，查找某一个数字
# 定义一个无序的列表
nums = [3,4,5,67,8,9,124,1541,56,23637,7,37,321,21,61,515,1]
nums.sort() # 给列表排序
print(nums)
# 运行结果：[1,3,4,5,7,8,9,21,37,56,61,67,124,321,515,1541,23637]
nums = [-2,3,4,6,13,23,56,74,251,562,7437]
find_num = 13
# 方案一：整体遍历效率太低
for num in nums:
if num == find_num:
print("find it")
break
# for循环的弊端：效率低，得看运气。
# 使用二分法：从中间开始找，伪代码
def binary_search(find_num,列表)：
mid_val=找列表中间的值
if find_num > mid_val:
# 应该在列表的右半部分查找
# (1) 新列表 = 列表切片右半部分
# (2) 重复本身的代码(列表)
elif find_num < mid_val:
# 应该在列表的左半部分
# (3)新列表 = 列表切左半部分
# (4)重复本身的代码(列表)
else: # find_num= mid_val
# 找到了
print('find it')
# 使用交互式程序获取应该列表的索引取值
nums = [1,2,3,4,5] # 定义一个含有奇数个的列表
len(nums) // 2 # 获取这个列表的中间索引值
3 # 这个列表的中间索引值是3
# 优化：二分法+递归解决需求
nunms = [-2,3,4,6,13,23,56,74,251,562,7437]
find_num = 15
def binary search(find num,1):
# 查看调用列表的次数
print(1)
# 针对列表索引值超范围:IndexError:list indx out of range
if len(1) == 0:
print("找的值不存在！！")
return
mid_index = len(1) // 2 # 获取列表中间的索引
if find_num > 1[mid_index]:
1 = 1[mid_index + 1:] # 列表切片，从中间索引加1处到列表最后。
binary_search(find_num,1)
elif find_num < 1[mid_index]:
1 = 1[:mid_index] # 列表切片，从列表到中间索引处。
binary_search(find_num,1)
else:
print('find it')
binary_search(find_num,nums)
# 优化：二分法+递归解决需求
nums = [-2,3,4,6,13,23,56,74,251,562,7437]
find_num = 15
def binary_search(find_num,l):
# 查看调用列表的次数
print(l)
# 针对列表索引值超出范围：IndexError: list index out of range
if len(l) == 0:
print("找的值不存在！！")
return
mid_index = len(l) // 2 # 获取列表中间值的索引
if find_num > l[mid_index]:
l = l[mid_index + 1:] # 列表切片，从中间索引加1处到列表最后。
binary_search(find_num,l)
elif find_num < l[mid_index]:
l = l[:mid_index] # 列表切片，从列表头到中间索引处。
binary_search(find_num,l)
else:
print('find it')
binary_search(find_num,nums)
# 第二次优化递归实现二分法：加入返回值
nums = [-3,4,7,10,13,21,43,77,89]
# find_num = 3
def binary_search(find_num,l):
print(l)
if len(l) == 0:
print("该值不存在！！！")
return False
mid_index = len(l) // 2
if find_num > l[mid_index]:
l = l[mid_index:1]
return binary_search(find_num,l)
elif find_num < l[mid_index]:
l = l[:mid_index]
return binary_search(find_num,l)
else:
print('find it')
return True
res = binary_search(7,nums)
print(res)
"""运行结果;没有return返回None
[-3, 4, 7, 10, 13, 21, 43, 77, 89]
[-3, 4, 7, 10]
find it
None
"""
# 获取结果的返回值：运行返回值是None？为啥？这要追溯到函数运行时的运行结果，没有return返回None
"""加入return后运行结果：
[-3, 4, 7, 10, 13, 21, 43, 77, 89]
[-3, 4, 7, 10]
find it
True
"""
三元表达式
三元表达式是一种python对于控制流程语句进行简写的形式。
res = 条件成立时返回的值 if 条件 else 条件不成立时返回的值
def max2(x,y):
if x > y:
return
else:
return y
res = max2(1,2)
各种生成式/表达式/推导式
name_list = ['jason', 'kevin', 'oscar', 'tony', 'jerry']
# 给列表中所有人名的后面加上_NB的后缀
# for循环
new_list = []
for name in name_list:
data = f'{name}_NB'
new_list.append(data)
print(new_list)
# 列表生成式
# 先看for循环 每次for循环之后再看for关键字前面的操作
new_list = [name + "_NB" for name in name_list]
print(new_list)
# 复杂情况
new_list = [name + "_NB" for name in name_list if name == 'jason']
print(new_list)
new_list = ['大佬' if name == 'jason' else '小赤佬' for name in name_list if name != 'jack']
print(new_list)
# 字典生成式
s1 = 'hello world'
for i,j in enumerate(s1,start=100):
print(i,j)
d1 = {i: j for i, j in enumerate('hello')}
print(d1)
# 集合生成式
res = {i for i in 'hello'}
print(res)
# 元组生成式>>>:没有元组生成式 下列的结果是生成器(后面讲)
res = (i+'SB' for i in 'hello')
print(res)
for i in res:
print(i)
匿名函数
没有名字的函数 需要使用关键字lambda
语法结构
lambda 形参:返回值
使用场景
lambda a,b:a+b
匿名函数一般不单独使用 需要配合其他函数一起用
常见内置函数
1.map() 映射
l1 = [1, 2, 3, 4, 5]
def func(a):
return a + 1
res = map(lambda x:x+1, l1)
print(list(res))
2.max()\min()
l1 = [11, 22, 33, 44]
res = max(l1)
d1 = {
'zj': 100,
'jason': 8888,
'berk': 99999999,
'oscar': 1
}
def func(a):
return d1.get(a)
res = max(d1, key=lambda k: d1.get(k))
res = max(d1, key=func)
print(res)
3.reduce
reduce 传多个值 返回一个值
from functools import reduce
l1 = [11, 22, 33, 44, 55, 66, 77, 88]
res = reduce(lambda a, b: a * b, l1)
print(res)
'''好奇执行流程可以使用debug模式简单看看'''