Python数据结构分而治之

在分割与征服方法中，手头的问题被分割成更小的子问题，然后每个问题被独立解决。当我们继续将子问题划分为更小的子问题时，我们最终可能会达到一个不可能再划分的阶段。那些 “原子式 “的最小可能的子问题（分数）被解决了。所有子问题的解决方案最终被合并，以获得一个原始问题的解决方案。

Python - 分割和征服

大体上，我们可以用三步法来理解 分而治之 的方法。

分割/断裂

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

征服/解决

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

合并/梳理

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

例子

下面的程序是一个 分而治之 的编程方法的例子，二进制搜索是用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))

输出

当上述代码被执行时，它产生了以下结果 –