Python 分而治之
Python 分而治之
Python 分而治之详细操作教程
在分而治之的方法中，将手头的问题分成较小的子问题，然后分别解决每个问题。当我们继续将子问题划分为更小的子问题时，我们最终可能会达到无法再进行划分的阶段。那些“原子的”最小可能的子问题（分数）得以解决。最后合并所有子问题的解决方案，以获得原始问题的解决方案。
从广义上讲，我们可以通过三步过程来理解分而治之的方法。
分割/断裂
此步骤涉及将问题分解为较小的子问题。子问题应该代表原始问题的一部分。此步骤通常采用递归方法来划分问题，直到没有子问题可以进一步分割为止。在这个阶段，子问题本质上已成为原子问题，但仍代表实际问题的一部分。
解决
此步骤收到许多要解决的较小子问题。通常，在此级别上，问题被认为是“已解决”。
合并
解决了较小的子问题后，此阶段将它们递归组合，直到它们为原始问题制定了解决方案。这种算法方法递归起作用，征服和合并步骤如此接近，以至于它们看起来像一个。
实例
以下程序是分治式编程方法的示例，其中使用python实现二进制搜索。
二进制搜索实现
在二进制搜索中，我们获取元素的排序列表，然后开始在列表中间查找元素。如果搜索值与列表中的中间值匹配，我们将完成搜索。否则，我们根据搜索项目的值来选择是继续处理列表的右半边还是左半部分，从而消除元素列表的一半。由于列表已排序，因此这比线性搜索要快得多。在这里，我们划分给定的列表，并通过选择列表的适当一半来征服。我们重复此方法直到找到元素或得出列表中不存在该元素的结论。
# Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
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