Python——分而治之

---

在分而治之的方法中，手头的问题被分成更小的子问题，然后独立解决每个问题。当我们继续将子问题划分为更小的子问题时，我们最终可能会达到无法再划分的阶段。解决那些“Atomics”最小可能的子问题（分数）。最后将所有子问题的解合并，得到原问题的解。

从广义上讲，我们可以通过三步过程来理解分而治之的方法。

划分/打破

此步骤涉及将问题分解为更小的子问题。子问题应该代表原始问题的一部分。这一步一般采用递归的方式来划分问题，直到没有子问题可进一步整除为止。在此阶段，子问题本质上变成Atomics问题，但仍然代表实际问题的某些部分。

征服/解决

这一步接收到许多需要解决的较小的子问题。一般来说，在这个级别上，问题被认为是自行“解决”的。

合并/组合

当较小的子问题得到解决后，此阶段会递归地组合它们，直到它们形成原始问题的解决方案。这种算法方法递归地工作并克服了问题。合并步骤的工作原理非常接近，以至于它们看起来像是一个。

例子

以下程序是分而治之编程方法的示例，其中使用 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