Divide and conquer

优质

小牛编辑

130浏览

2023-12-01

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

从广义上讲，我们可以通过三个步骤来理解divide-and-conquer方法。

Divide/Break

此步骤涉及将问题分解为更小的子问题。子问题应该代表原始问题的一部分。此步骤通常采用递归方法来划分问题，直到子问题不再可被整除为止。在这个阶段，子问题本质上是原子的，但仍然代表了实际问题的某些部分。

Conquer/Solve

这一步收到了许多较小的子问题需要解决。通常，在这个层面上，问题被认为是自己“解决”的。

Merge/Combine

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

例子 (Examples)

以下程序是divide-and-conquer编程方法的示例，其中使用python实现二进制搜索。

二进制搜索实现

在二进制搜索中，我们采用排序的元素列表，并开始在列表中间查找元素。如果搜索值与列表中的中间值匹配，则我们完成搜索。否则，我们通过选择是否根据所搜索项目的值继续处理列表的右半部分或左半部分来清除元素列表的一半。这是可能的，因为列表是排序的，它比线性搜索快得多。在这里，我们通过选择列表的正确一半来划分给定列表并征服。我们重复这个approcah，直到我们找到该元素或者在列表中找不到它。

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