可以分為三個步驟：
1.分解：將問題分解為若干個相互獨立，規(guī)模較小，與原問題形式相同的子問題，確保每個小問題的解法結(jié)構(gòu)，形式結(jié)構(gòu)相同。
2.解決：若可以對子問題進(jìn)行解決，則進(jìn)行對子問題的解決，若不可以，則繼續(xù)拆分，可能是一個遞歸的過程。
3.合并

遞歸過程的偽代碼：

T  DivideAndConquer(P){
    if(P 可以直接進(jìn)行解決){
            T<--P的解決結(jié)果
            return T             
      }
  將P分解為子問題{P1,P2,P3.......Pn}
  for_each(Pi:{P1,P2,P3.......Pn}){
    ti<--DivideAndConquer(Pi) //遞歸解決子問題Pi
  }  
    T<--Merge(t1,t2.....tn) //合并子問題的解
    returnT
}

能使用分治法解決的問題一般都具有兩個顯著的特點，
第一個特點是
問題可以分解為若干個規(guī)模較小的相同問題，并且這個分解關(guān)系可以用遞歸或遞推的方式逐級分解，直到問題的規(guī)模小到可以直接求解的程度。這里說的相同問題，并不是說分解后的子問題與原問題完全一樣，這里說的相同只是問題的結(jié)構(gòu)相同，比如原問題有四個屬性，分解后規(guī)模較小的子問題也應(yīng)該具有四個相同的屬性，不同的只是各個屬性的范圍和規(guī)模。
第二個特點是
子問題的解可以用某種方式合并出原始問題的解。這很容易理解，如果不能合并出原始問題的解，那么子問題的劃分和求解就沒有意義了。

分治法的難點是如何將子問題分解，并且將子問題的解合并出原始問題的解，針對不同的問題，通常有不同的分解與合并方式。先來看看快速排序算法，快速排序算法的分解思想是選擇一個標(biāo)兵數(shù)，將待排序的序列分成兩個子序列，其中一個子序列中的數(shù)都小于標(biāo)兵數(shù)，另一個子序列中的數(shù)都大于標(biāo)兵數(shù)，然后分別對這兩個子序列排序，其合并思想就是將兩個已經(jīng)排序的子序列一前一后拼接在標(biāo)兵數(shù)前后，組成一個完整的有序序列

分治法的例子：字符串全排列問題

我們的問題是：給定一個沒有重復(fù)字母的字符串，輸出該字符串中字符的所有排列。假如給定的字符串是“abc”，則應(yīng)該輸出“abc”、“acb”、“bac”、“bca”、“cab”和“cba”六種結(jié)果。
首先分析這是一個全排列問題，解決這個問題我們的常用策略是每次選擇固定一個字符，然后對剩下的兩個字符進(jìn)行排列。比如這個三個字母的字符串，我們首先選擇固定 a，然后對 bc 進(jìn)行排列，可以得到“abc”和“acb”兩個結(jié)果；然后選擇固定 b，對 ac 進(jìn)行排列，可以得到“bac”和“bca”兩個結(jié)果；最后選擇固定 c，對 ab 排列，可以得到“cab”和“cba”兩個結(jié)果。
不知道大家有沒有意識到，這其實就是使用了分治法的思想在解決問題。三個字符排列，我們?nèi)四X可能處理不過來，但是我們固定一個字母后，把問題的規(guī)模減小為兩個字符的排列，兩個字符的排列只有兩種結(jié)果，是可以解決的問題；然后我們將小問題的結(jié)果與固定的字母組合在一起，就可以得到原始問題，即三個字符的排列結(jié)果。分治法分解子問題，并不是一定要用某種方式均勻分解原始問題，哪怕是每次只能將原始問題的規(guī)模變小一點，也是一種分解子問題的方法。
回到我們這個問題上，對字符串類問題分解子問題，通?？紤]的方法有兩個。

-一個方法是用字符串的開始位置和字符串的長度表示一個子字符串，對于一個長度為 n 的字符串，用這種方法定義的子問題就是“從位置 i 開始，長度為 m 的字符串，原始問題就是從位置 1 開始，長度為 n 的字符串。
-另一個方法是用字符串的位置區(qū)間來表示一個子字符串，同樣對于一個長度為 n 的字符串，用這種方法定義的子問題就是“從位置 i 開始，到位置 j 結(jié)束的字符串，原始問題就是從位置 1 開始到位置 n 結(jié)束的字符串。

對于這個問題，我們選擇用區(qū)間的方法定義子問題，即用字符位置索引區(qū)間 [begin, end] 表示子問題，選好子問題的表達(dá)方式，接下來就要考慮如何分解子問題。根據(jù)之前的分析，我們采用每次固定一個字符，然后將剩下的字符串作為一個子問題進(jìn)行全排列的方式分解子問題。因為每個字符都要被“固定”一次，所以算法實現(xiàn)的方法是用一個循環(huán)對子問題 [begin, end] 區(qū)間上的每個字符都選擇一次。

我們采用的方法是將問題區(qū)間 [begin, end] 中的 begin 位置作為選中的固定字符位置，將除了這個位置之外的問題區(qū)間 [begin+1, end] 作為子問題進(jìn)一步處理。如果被選中的固定字符不在 begin 位置，則交換兩個字符的位置，使得被選中的固定字符位于 begin 位置。

解決了子問題的分解，接下來要考慮子問題的求解。分解的目的是為了減小問題的規(guī)模，直到問題能夠求解，對于這個字符串排列問題，當(dāng)子問題的規(guī)模減小到只有一個字符的時候，子問題就可以求解了。因為我們處理方式是從前向后，每次固定 begin 位置的字符，然后將區(qū)間 [begin+1, end] 作為子問題進(jìn)一步處理，所以當(dāng) begin 位置和 end 位置相同的時候，就說明字符串只有一個字符了，這時就不需要再分解子問題了。

void swap (String[] std,int begin,int i){
  if (begin!= i)
    {
        int tmp = std[begin]; 
        std[begin] = std[i];
        std[i] = tmp;
    }

}


void solution(String[] std,int begin,int end)
{
  if(begin==end){
   syso(std)
}
for(int i=begin;i<=end;i++){
  swap(std,begin,i);//把第 i 個字符換到 begin 位置
  solution(std,begin+1,end);//子問題
   swap(std,begin,i);//在挑選下一個固定字符之前，需要換回來
}

}

二分查找

  //循環(huán)實現(xiàn)二分算法 
    public static int binSearch_1(int key, int[] array) { 
        int low = 0; //第一個下標(biāo)
        int high = array.length - 1;//最后一個下標(biāo)
        int middle = 0; //防越界
        if (key < array[low] || key > array[high] || low > high) { 
              return -1;
        } while (low <= high) {
            middle = (low + high) / 2; 
            if (middle == key) { 
              return array[middle];
            } else if (middle < key) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
        } 
      return -1;
    } 
      /* *遞歸實現(xiàn)二分算法 */
    public static int binSearch_2(int key,int[] array,int low,int high){
     //防越界
        if (key < array[low] || key > array[high] || low > high) { 
          return -1;
        }
           int middle = (low+high)/2; 
            if(array[middle]>key){ //大于關(guān)鍵字
            return  binSearch_2(key,array,low,middle-1);
        }else if(array[middle]<key){ //小于關(guān)鍵字
            return binSearch_2(key,array,middle+1,high);
        }else{ 
          return array[middle];
        }
    }
}

二分查找中中間值的計算：

這是一個經(jīng)典的話題，如何計算二分查找中的中值？大家一般給出了兩種計算方法：

算法一： mid = (low + high) / 2
算法二： mid = low + (high – low)/2

乍看起來，算法一簡潔，算法二提取之后，跟算法一沒有什么區(qū)別。但是實際上，區(qū)別是存在的。算法一的做法，在極端情況下，(low + high)存在著溢出的風(fēng)險，進(jìn)而得到錯誤的mid結(jié)果，導(dǎo)致程序錯誤。而算法二能夠保證計算出來的mid，一定大于low，小于high，不存在溢出的問題。