Python中使用分治法找第二大元素

已知n个元素存在，确定第二大的元素值。若采用线性扫描的方式来处理该问题的话。

首先找出最大值，比较n-1次

然后从n-1个元素中找出最大值，比较n-2次

下面考虑设计一个选第二大元素的分治算法

1.将n个元素从中间一分为二

使用递归来处理两个子问题，在每个子问题中计算其最大值，并将被淘汰的小者记录于对应较大者的列表中。从被最大值淘汰后的剩余较大者列表中寻找次大者

实现

将较大的元素淘汰后的结果存储在字典中进行处理，在这种情况下每个键对应于给定的一组原始数据集合。其值则对应于一个包含所有被淘汰结果的具体列表信息

首先构建一个名为find_max()的功能模块来完成第一阶段的具体操作：该模块将接受包含n个元素的列表a_list以及界定问题范围的关键参数left和right作为输入参数。其主要功能是计算并返回所有输入元素中的最大值，并将不符合条件的淘汰项按照对应的键信息整合到目标字典中

 def find_max(arr,left,right):

    
     global dic
    
     if left>=right:
    
     return arr[left]
    
     mid=(left+right)//2
    
     left_max=find_max(arr,left,mid)