Can you summarize the following document?
        
  折半搜尋演算法——一個將原來問題連逐地拆細成大約一半大小的單一子問題的分治演算法——擁有一段悠長歴史。雖然演算法在計算機上的清楚描述出現在1946年約翰莫齊利(John Mauchly)的一篇文章裡,然而利用已排序的物件序列去加快搜尋的構想早已在公元前200年的巴比倫尼亞出現。另一個單一子問題的分治演算法是找出2個數的最大公因子的輾轉相除法(透過將數字化小至使子問題變得簡單),於公元前數世紀已經出現。  一個早期有多個子問題的分治演算法是高斯在1805年描述關於快速傅立葉奱換的演算法,儘管他沒有量化地分析它的運算元目,而快速傅立葉奱換直至在一世紀之後被重新發現之前亦沒有廣泛流傳。這個演算法現在稱為庫利-圖基快速傅立葉變換演算法。  至於專門用於計算機之上而且正確地分析的分治演算法早期例子,則可以數到約翰·馮·諾伊曼於1945年發明的歸併排序。  另一個顯著的例子是Anatolii Alexeevitch Karatsuba於1960年發明在formula_1步驟內將兩個n位數相乘的Karatsuba演算法。它反證了安德雷·柯爾莫哥洛夫於1956年認為這個乘法需要formula_2步驟的猜想。  高德納舉了一個最初並沒有涉及計算機的分治演算法例子,就是一般郵局用於分發信件的方法:信件在主要郵局根據不同的地理範圍而分到不同的袋裡,每個袋亦在運送到地區郵局時分到更小的袋裡,如是者直至信件被派發為止。這個方法與早於1929年的打孔卡排序機所用的基數排序相類同。

  

  分治演算法是一個解決複雜問題的好工具,它可以把問題分解成若干個子問題,把子問題逐個解決,再組合到一起形成大問題的答案。比如,漢諾塔問題如果採用分治演算法,可以把高度為n的塔的問題轉換成高度為n-1的塔來解決,如此重複,直至問題化簡到可以很容易的處理為止。

  人們發現有很多效率很高的分治演算法,比如,Karatsuba快速乘法演算法、快速排序演算法和並行演算法、矩陣乘法的施特拉森演算法、快速傅立葉變換等。

  

  在每一層遞迴上都有三個步驟:

  分治法在高階語言中主要的一個思想是遞迴,LISP語言中的體現出了極豐富的分治法。  以下是歸併排序C語言的示例程式碼,輸入引數中,需要排序的陣列為array[],起始索引為first,終止索引為last。呼叫完成後,array[]中從first到last處於升序排列。  在程式中可以看出分治法的應用:在merge_sort()中,將原來針對索引first到last的陣列排序的問題,分為二份較小的問題 最後再進行二個陣列的合併。
在電腦科學中,分治法是建基於多項分支遞迴的一種很重要的演算法正規化。字面上的解釋是“分而治之”,就是把一個複雜的問題分成兩個或更多的相同或相似的子問題,直到最後子問題可以簡單的直接求解,原問題的解即子問題的解的合併。