python 分而治之

在分而治之的方法中，手中的問題被分成較小的子問題，然后每個問題都是獨(dú)立解決的。當(dāng)我們繼續(xù)將子問題分解成更小的子問題時，我們最終可能會達(dá)到不可能再分裂的階段。這些“原子”最小可能的子問題（分?jǐn)?shù)）被解決。所有子問題的解決方案最終被合并以獲得原始問題的解決方案。

大體而言，我們可以通過三個步驟理解 分而治之的 方法。

分割/歇

這一步涉及將問題分解成更小的子問題。子問題應(yīng)該是原始問題的一部分。這一步通常采用遞歸方法來分解問題，直到?jīng)]有子問題可以進(jìn)一步劃分為止。在這個階段，子問題本質(zhì)上是原子性的，但仍然是實(shí)際問題的一部分。

征服/解決

這一步收到很多較小的子問題需要解決。一般來說，在這個層面上，問題被認(rèn)為是自己解決的。

合并/合并

當(dāng)較小的子問題得到解決時，這個階段遞歸地將它們結(jié)合起來，直到他們制定原始問題的解決方案。這種算法方法遞歸地工作，并且征服和合并步驟工作得如此之近，以至于它們看起來像一個。

例子

以下程序是使用python實(shí)現(xiàn)二進(jìn)制搜索的 分而治之 編程方法的示例。

二進(jìn)制搜索實(shí)現(xiàn)

在二進(jìn)制搜索中，我們采用排序的元素列表并開始在列表中間尋找元素。如果搜索值與列表中的中間值匹配，我們完成搜索。否則，我們通過選擇是否根據(jù)搜索到的項(xiàng)目的值來處理列表的右半部分或左半部分來列出元素列表的一半。這是可能的，因?yàn)榱斜砼判虿⑶冶染€性搜索快得多。在這里，我們通過選擇列表的適當(dāng)?shù)囊话雭韯澐纸o定列表并征服。我們重復(fù)這個步驟，直到找到元素或者在列表中得出結(jié)論。

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))

當(dāng)上面的代碼被執(zhí)行時，它會產(chǎn)生以下結(jié)果：

5
none