分治算法

陈新龙

今天我们来学习新的Python算法——分治。

分治：我们将一个复杂的问题分成两个或更多的相同或类似的子问题，再把子问题分成更小的子问题（分），这些子问题可以简单地直接求解（治），最后将所有子问题的解合并起来就是原问题的解（合）。

分治算法适用于数据规模较大的问题，通过分治算法，将数据分解到多个小问题，直到找到正确答案为止。

例如我们想求解一个列表中的最大值或者最小值，為了体会分治算法，不使用Python中的max（）或min（）函数，而采用分治函数来解决。在列表中存在很多数据，我们将比较的数据不断缩小再缩小，当数据规模为2时只需一个判断就可以找到其中的最小值了。

这个求最值的问题就变成将若干数值不断分组直到两个数据进行比较，通过递归把数据不断从中间划分开，直到其规模小于等于2时，比较返回结果，继续通过递归到最后两个数据比较就可以找到最值了。

在这个程序中对数据使用递归的方法拆分数据，将数据分成两个部分left_list和right_list，当数据的规模等于1的时候可直接判断最值，当数据的规模等于2的时候通过比较可以判断出最值。通过递归与分治的方法便求出列表中的最大值是99了。

如果你真正掌握了分治的原理，那么可以尝试做一道题目：“判断某个元素是否在列表中，如果存在，元素输出，如果不存在，显示该数字不存在。”期待你的答案哦。