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