Python - 分治算法

在分而治之的方法中，将手头的问题分成较小的子问题，然后分别解决每个问题，当无涯教程继续将子问题划分为更小的子问题时，最终可能会达到无法再进行划分的阶段。那些原子的最小可能的子问题得以解决，最后合并所有子问题的解决方案，以获得原始问题的解决方案。

二分搜索实现

在二分搜索中，获取元素的排序列表，然后开始在列表中间寻找元素，如果搜索值匹配 使用列表中的中间值完成了搜索，否则，通过选择是否继续将一半列表的右半部分或左半部分，取决于搜索元素的值，由于列表已排序，因此这比线性搜索要快得多。 

def bsearch(list, val):

    list_size=len(list) - 1

    idx0=0
    idxn=list_size
# 找到中间的最大值

    while idx0 <= idxn:
        midval=(idx0 + idxn)//2

        if list[midval] == val:
            return midval
# 比较中间最值的值
        if val > list[midval]:
            idx0=midval + 1
        else:
            idxn=midval - 1

    if idx0 > idxn:
        return None
# 初始化排序列表
list=[2,7,19,34,53,72]

# 打印搜索结果
print(bsearch(list,72))
print(bsearch(list,11))

执行以上代码后，将产生以下输出:

链接：https://www.learnfk.comhttps://www.learnfk.com/python-data-structure/python-divide-and-conquer.html

来源：LearnFk无涯教程网

5
None