2. 分治算法查找数组（序列）中最大值或最小值的算法有很多，接下来我们以 [12,16,7,9,8] 序列为例讲解两种查找最值的算法。
3. 普通循环对比获取最大值和最小值分治算法解决问题的思路是：先将整个问题拆分成多个相互独立且数据量更少的小问题，通过逐一解决这些简单的小问题，最终找到解决整个问题的方案。
- 如果列表没有值，直接返回-1；
- 将列表中的第一个值赋值给min和max，默认最大和最小；
- 循环列表，获取当前值和min或max进行对比；
- 当 min > cur_value，更新 min = cur_value；
- 当 max < cur_value，更新 max = cur_value；
- 循环完成，返回min和max。
# 通过对比获取最大或最小值
def get_max_and_min(arr):
if len(arr) == 0:
return - 1
min = arr[0]
max = arr[0]
for i in range(1,len(arr)):
cur_value = arr[i]
if min > cur_value:
min = cur_value
if max < cur_value:
max = cur_value
return { 'min': min, 'max': max }
4. 分治算法获取最大值
4.1 代码分析
- 如果列表长度是0，直接返回-1，表示没找到最大值；
- 当分区只有2个值时，获取其中最大的返回
- 将列表分割成两个区域；
- 获取列表的中间位置index；
- 递归回调，获取左边列表的最大值；
- 递归回调，获取右边列表的最大值；
- 注意：此处切割，会将列表不断的分，直到列表中只存在一个或两个元素时，获取最大的返回，然后再左边和右边比较，返回最大值。
# 通过分治法获取列表中的最大值
def get_max(arr, left, right):
# 如果列表长度是0，直接返回-1，表示没找到最大值
if len(arr) == 0:
return - 1
# 当分区只有2个值时，获取其中最大的返回
if right - left <= 1:
if arr[left] >= arr[right]:
return arr[left]
return arr[right]
return get_split_two_area_max(arr, left, right)
def get_split_two_area_max(arr, left, right):
# 计算列表的中间值,将列表等分为两个区域
middle = int((left + right) / 2 + left)
left_max = get_max(arr, left, middle)
right_max = get_max(arr, middle + 1, right)
if left_max >= right_max:
return left_max
else:
return right_max
4.2 注意：列表元素超过5，会导致递归报错！
5. 分治算法获取最小值 5.1 求最小值代码分析RecursionError: maximum recursion depth exceeded while calling a Python object
- 如果列表长度是0，直接返回-1，表示没找到最小值；
- 当分区只有2个值时，获取其中最小的返回
- 将列表分割成两个区域；
- 获取列表的中间位置index；
- 递归回调，获取左边列表的最小值；
- 递归回调，获取右边列表的最小值；
- 注意：此处切割，会将列表不断的分，直到列表中只存在一个或两个元素时，获取最小的返回，然后再左边和右边比较，返回最小值。
# 通过分治算法，获取列表中的最小值
def get_min(arr, left, right):
if len(arr) == 0:
return -1
if right - left <= 1:
if arr[left] <= arr[right]:
return arr[left]
return arr[right]
mid = int((left + right) / 2 + left)
min_left = get_min(arr, left, mid)
min_right = get_min(arr, mid + 1, right)
if min_left <= min_right:
return min_left
else:
return min_right
5.2 注意：列表元素超过5，会导致递归报错！
6. 完整代码RecursionError: maximum recursion depth exceeded while calling a Python object
'''
Descripttion:
version: 1.0.0
Author: Rattenking
Date: 2022-07-12 16:16:48
LastEditors: Rattenking
'''
# 通过分治法获取列表中的最大值
def get_max(arr, left, right):
# 如果列表长度是0，直接返回-1，表示没找到最大值
if len(arr) == 0:
return - 1
# 当分区只有2个值时，获取其中最大的返回
if right - left <= 1:
if arr[left] >= arr[right]:
return arr[left]
return arr[right]
return get_split_two_area_max(arr, left, right)
def get_split_two_area_max(arr, left, right):
# 计算列表的中间值,将列表等分为两个区域
middle = int((left + right) / 2 + left)
left_max = get_max(arr, left, middle)
right_max = get_max(arr, middle + 1, right)
if left_max >= right_max:
return left_max
else:
return right_max
# 通过分治算法，获取列表中的最小值
def get_min(arr, left, right):
if len(arr) == 0:
return -1
if right - left <= 1:
if arr[left] <= arr[right]:
return arr[left]
return arr[right]
mid = int((left + right) / 2 + left)
min_left = get_min(arr, left, mid)
min_right = get_min(arr, mid + 1, right)
if min_left <= min_right:
return min_left
else:
return min_right
# 通过对比获取最大或最小值
def get_max_and_min(arr):
if len(arr) == 0:
return - 1
min = arr[0]
max = arr[0]
for i in range(1,len(arr)):
cur_value = arr[i]
if min > cur_value:
min = cur_value
if max < cur_value:
max = cur_value
return { 'min': min, 'max': max }
if __name__ == '__main__':
lists = [12,16,7,9,8]
max = get_max(lists, 0, len(lists) - 1)
print("最大值：", max)
min = get_min(lists, 0, len(lists) - 1)
print("最小值：", min)
# 通过对比获取列表中的最大值和最小值
min_and_max = get_max_and_min(lists)
print("最大值：", min_and_max['max'])
print("最小值：", min_and_max['min'])
7. 执行结果
WXRUI体验二维码
下载
我的博客，欢迎交流！
我的CSDN博客，欢迎交流！
微信小程序专栏
前端笔记专栏
微信小程序实现部分高德地图功能的DEMO下载
微信小程序实现MUI的部分效果的DEMO下载
微信小程序实现MUI的GIT项目地址
微信小程序实例列表
前端笔记列表
游戏列表
暑期编程PK赛 得CSDN机械键盘等精美礼品！
