Python算法——分治法查找数组中元素最小最大值_分治法 最大和最小查询次数

要求：

       给定数组a1,a2,a3,...an，找出数组中最大值和最小值。（数组中两两各不相同）

分析：

       算法思想类似于上图，将数组两两分为一组，如果数组元素奇数个，就把最后一个元素单独分为一组，然后分别对每一组中相邻两个元素比较，把二者中值小的数放在数组左边，值大的数放在数组右边，只需比较n/2次就可以将数组分组完成。这时候最小值在每一组左边部分，最大值在每一组右边部分，接着在每一组左边部分找最小值，右边部分找最大值，查找分别需比较n/2-1次和 n/2-1次。因此，总共比较次数约为(n/2)+(n/2-1)+(n/2-1)=3n/2-2次。

实现代码：

# -*- coding:utf-8 -*-
class MaxMin():
    def __init__(self):
        self.max = None
        self.min = None
    def getMax(self):
        return self.max
    def getMin(self):
        return self.min
    def GetmaxAndmin(self,arr):
        if arr==None:
            print("参数不合法")
            return