Divide and Conquer分治

算法原理：

将一个数组元素大于 2 的数组分成两个子数组，然后对每一个子数组递归调用，直到最小的子数组的元素个数为 1 个或者是 2 个，此时就能直接得出最大值与最小值，然后逐步往上合并子数组，比较 2 个子数组的最大值与最小值，依次进行下去，最后就能找到整个数组的最大值与最小值。

解题步骤：

① 先解决小规模的问题，如数组中只有 1 个元素或者只有两个元素时候的情况；

② 将问题分解，如果数组的元素大于等于 3 个，将数组分为两个小的数组；
③ 递归的求解各子问题，将② 中分解的两个小的数组再进行以上两个步骤最后都化为小规模问题解决；
④ 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

例如：在n个元素中找出最大元素和最小元素。[-13，13，9，-5，7，23，0，15]
用直接比较法求出：

分治：
把n个元素分成两组；
分别求两组的最大值和最小值；
然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。
<如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。>

import time
def findbest(A, low, high):
    if high - low <= 1:                 #如果数组中元素只剩下两个，则可以直接比较
        if A[low] <= A[high]:
            return A[high], A[low]
        else:
            return A[low], A[high]
    mid = (low + high) // 2             #从中点分成两个子数组，进行递归查找
    result1 = findbest(A, low, mid)
    result2 = findbest(A, mid+1, high)
    if result1[0] < result2[0]:         #比较找到的两个子数组的最大值的大小关系
        if result1[1] < result2[1]:     #再比较找到的两个子数组的最小值的大小关系
            return result2[0], result1[1]   #返回结果（最大值，最小值）
        else:
            return result2[0], result2[1]
    else:
        if result1[1] < result2[1]:
            return result1[0], result1[1]
        else:
            return result1[0], result2[1]
def main():
    from random import sample
    rand_array = sample([x for x in range(-1000, 1000)], 10)#在-1000~999中产生10个随机数
    print(rand_array)
    start = time.time()
    result = findbest(rand_array, 0, 9)
    print("最大值为：%d" %(result[0]))
    print("最小值为：%d" %(result[1]))
    end = time.time()
    print("共耗时:\n" + str(end - start) + " s")
if __name__ == '__main__':
    main()