Python 分而治之

在分而治之的方法中，手中的问题被分成较小的子问题，然后每个问题都是独立解决的。当我们继续将子问题分解成更小的子问题时，我们最终可能会达到不可能再分裂的阶段。这些“原子”最小可能的子问题（分数）被解决。所有子问题的解决方案最终被合并以获得原始问题的解决方案。

分而治之

大体而言，我们可以通过三个步骤理解 分而治之的 方法。

分割/歇

这一步涉及将问题分解成更小的子问题。子问题应该是原始问题的一部分。这一步通常采用递归方法来分解问题，直到没有子问题可以进一步划分为止。在这个阶段，子问题本质上是原子性的，但仍然是实际问题的一部分。

征服/解决

这一步收到很多较小的子问题需要解决。一般来说，在这个层面上，问题被认为是自己解决的。

合并/合并

当较小的子问题得到解决时，这个阶段递归地将它们结合起来，直到他们制定原始问题的解决方案。这种算法方法递归地工作，并且征服和合并步骤工作得如此之近，以至于它们看起来像一个。

例子

以下程序是使用python实现二进制搜索的 分而治之 编程方法的示例。

二进制搜索实现

在二进制搜索中，我们采用排序的元素列表并开始在列表中间寻找元素。如果搜索值与列表中的中间值匹配，我们完成搜索。否则，我们通过选择是否根据搜索到的项目的值来处理列表的右半部分或左半部分来列出元素列表的一半。这是可能的，因为列表排序并且比线性搜索快得多。在这里，我们通过选择列表的适当的一半来划分给定列表并征服。我们重复这个步骤，直到找到元素或者在列表中得出结论。

def bsearch(list, val):

    list_size = len(list) - 1

    idx0 = 0
    idxn = list_size
# Find the middle most value

    while idx0 <= idxn:
        midval = (idx0 + idxn)// 2

        if list[midval] == val:
            return midval
# Compare the value the middle most value
        if val > list[midval]:
            idx0 = midval + 1
        else:
            idxn = midval - 1

    if idx0 > idxn:
        return None
# Initialize the sorted list
list = [2,7,19,34,53,72]

# Print the search result
print(bsearch(list,72))
print(bsearch(list,11))

当上面的代码被执行时，它会产生以下结果：

5
None

下一章：Python 递归

递归允许函数自行调用。修复代码的步骤会一次又一次地执行新值。我们还必须设置判断递归调用何时结束的标准。在下面的例子中，我们看到了二进制搜索的递归方法。我们采用一个排序列表，并将其索引范围作为递归函数的输入。使 ...

上一章：Python 算法分析

下一章：Python 递归