python 分而治之

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

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

分割/歇

這一步涉及將問題分解成更小的子問題。子問題應該是原始問題的一部分。這一步通常采用遞歸方法來分解問題，直到沒有子問題可以進一步劃分為止。在這個階段，子問題本質上是原子性的，但仍然是實際問題的一部分。

征服/解決

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

合并/合并

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

例子

以下程序是使用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