上一节:
下一节:

  Python - 数据结构之分治法

  • 简述

    在分治法中，手头的问题被分成更小的子问题，然后每个问题独立解决。当我们继续将子问题划分为更小的子问题时，我们最终可能会到达一个无法再划分的阶段。解决了那些“原子”最小的可能子问题（分数）。最后合并所有子问题的解，得到原问题的解。
    分治法
    大体上，我们可以理解divide-and-conquer方法分为三步。

  • 分割/中断

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

  • 征服/解决

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

  • 合并/合并

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

    例子

    下面的程序是一个例子divide-and-conquer使用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
上一节:
下一节: