分治法实现寻找最小值及所有最小值位置，python实现_最小值问题分治算法 py代码

python实现
A为输入的数组，begin与end是指向当前小数组头尾
min是最小值，minlist是保存对应最小值位置的数组

逻辑过程：（参考文末分治排序过程图，懒得专门画图了）
1.先把输入一次一次二分成为最小的问题（子数组），见代码中段递归调用自己
2.最小的问题是子数组只有一个元素，每个单个作为最小值和记录它位置的list，见代码前段终止条件及操作，但是A【begin】==min可能是多余操作，应该不会执行。
3.一层层合并，比对最小值，选小的返回给上一层，一样就把list合并，见代码后段。
可以设全局count记录basic operation次数

# count = 0
def find_mins(A,begin,end,min,minlist):
    '''设值结束情况，即分问题只有一个数字的情况'''
    if begin == end:
        if A[begin]< min:
            min = A[begin]
            minlist = [begin]
        elif A[begin]==min:
            minlist.append(begin)
        return min,minlist
    '''递归调用自己，分割问题，传递子问题所在子数组在原数组的的左右边界，
    后面两个用来记录当前情况，用户合并。'''
    tempmin1, tempminlist1 = find_mins(A,begin,int((begin+end)/2),min,minlist)
    tempmin2, tempminlist2 = find_mins(A,int((begin+end)/2+1),end,min,minlist)
    # global count
    # count=count+1
    '''归并，一层层把子问题的结果比较并且合并'''
    if tempmin1 < tempmin2:
        return tempmin1, tempminlist1
    elif tempmin1 > tempmin2:
        return tempmin2, tempminlist2
    elif tempmin1 == tempmin2:
        minlist = tempminlist1+tempminlist2
        return tempmin1, minlist

'''示例'''
A = [12,4,3125,21,100,5435,66,454,4,8,8,8,4]
min,minlist = find_mins(A,0,len(A)-1,100000,[])
print(str(min))
print(minlist)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

输入数组：
[12,4,3125,21,100,5435,66,454,4,8,8,8,4]
运行结果，显示最小值以及所有其所在的位置：
4
[1, 8, 12]

参考分治排序思想：