二分法查找

1、二分查找(​​Binary Search)
    　二分查找又稱折半查找，它是一種效率較高的查找方法。
    　二分查找要求：線性表是有序表，即表中結點按關鍵字有序，並且要用向量作為表的存儲結構。不妨設有序表是遞增有序的。

2、二分查找的基本想法
    　二分查找的基本觀念是：（設R[low..high]是目前的尋找區間）
 （1）先確定該區間的中點： 然後將待查的K值與R[mid].key比較：若相等，則查找成功並返回此位置，否則須確定新的查找區間，繼續二分查找，具體方法如下：
   　 ①若R[mid] .key>K，則由表的有序性可知R[mid..n].keys都大於K，因此若表中存在關鍵字等於K的結點，則該結點必定是在位置mid左邊的在子表R[1..mid-1]中，故新的查找區間是左子表R[1..mid-1]。
    　②類似地，若R[mid].key    　因此，從初始的查找區間R[1..n]開始，每經過一次與當前查找區間的中點位置上的結點關鍵字的比較，就可確定查找是否成功，不成功則當前的查找區間就縮小一半。此過程重複直至找到關鍵字為K的結點，或直到目前的查找區間為空(即查找失敗)為止。

3、二分查找演算法

    int BinSearch(SeqList R，KeyType K)

      { //在有序表R[1..n]中進行二分查找，成功時返回結點的位置，失敗時返回零
int low=1，high=n，mid； //置當前查找區間上、下界的初值
        while(low       low+high)/2；
          if(R[mid].key==K) return mid； //查找成功返回
          if(R[mid].kdy>K)
             high=mid-1; //繼續}R[low..mid-1]中找出
          else
             low=mid  return 0； //當low>high時表示查找區間為空，查找失敗
       } //BinSeareh
  二分查找演算法也很容易給出其遞歸程序【參見練習】

4、 二分查找演算法也很容易給出其遞歸程序【參見練習】

4、 二分查找演算法也很容易給出其遞歸程序【參見練習】

4、 二分查找演算法也很容易給出其遞歸程序【參見練習】

4、 二分查找演算法的執行過程 
　㟎

4、 二分查找算法序列為

    (05，13，19，21，37，56，64，75，80，88，92)
要找的關鍵字K分別是21和85。具體查找過程【參見動畫示範】

5、二分查找判定樹
    　二分查找過程可用二叉樹來描述：將目前查找區間的中間位置上的結點作為根，左子表和右子表中的結點分別作為根的左子樹和右子樹。由此得到的二元樹，稱為描述二分查找的判定樹(Decision Tree)或比較樹(Comparison Tree)。
  註：
    　判定樹的形態只與表結點個數n相關，而與輸入實例中R[1..n].keys的值無關。

  　【例】具有11個結點的有序表可用下圖所示的判定樹來表示。

   
          

（1）二分找出判定樹的組成

　　①圓結點即樹中的內部結點。樹中圓結點內的數字表示該結點在有序表中的位置。 🎜　　②外部結點：圓結點中的所有空指針均以一個虛擬的方形結點來取代，即外部結點。 🎜　 　③樹中某結點i與其左(右)孩子連接的左(右)分支上的標記""、")"表示：當待查關鍵字KR[i].key)時，應走左(右)分支到達i的左(右)孩子，將該孩子的關鍵字進一步和K比較。若相等，則查找 過程結束返回，否則繼續將K與樹中更下一層的結點比較。 🎜

（2）二分查找判定樹的查找
　　二分查找就是將給定值K與二分查找判定樹的根結點的關鍵字進行比較。若相等，成功。否則若小於根結點的關鍵字，請到左子樹尋找。若大於根結點的關鍵字，則到右子樹尋找。
　　【例】對於有11個結點的表，若查找的結點是表中第6個結點，則只需進行一次比較；若查找的結點是表中第3或第9個結點，則需進行二次比較；找第1，4，7，10個結點需要比較三次；找出第2，5，8，11個結點需要比較四次。
    　由此可見，成功的二分查找過程恰好是走了一條從判定樹的根到被查結點的路徑，經歷比較的關鍵字次數恰為該結點在樹中的層數。若查找失敗，則其比較過程是經歷了一條從判定樹根到某個外部結點的路徑，所需的關鍵字比較次數是該路徑上內部結點的總數。
    【例】待查表的關鍵字序列為：(05，13，19，21，37，56，64，75，80，88，92)，若要找K=85的記錄，所經過的內部結點為6、9、10，最後到達方形結點"9-10"，其比較次數為3。
    　實際上方形結點中"i-i+1"的含意為被查找值K是介於R[i].key和R[i+1].key之間的，即R[i].key

（3）二分查找的平均查找長度
     　設內部結點的總數為n=2h-1，則判定樹是深度為h=lg(n+1)的滿二叉樹(深度h不計外部結點) 。樹中第k層上的結點個數為2k-1，找出它們所需的比較次數是k。因此在等機率假設下，二分查找成功時的平均查找長度為：
           ASLbn≈lg(n+1)-1
　　二分找出在找出失敗時所需比較的關鍵字個數不超過判定樹的深度，判定樹的深度，判定樹的深度，在最壞情況下找出成功的比較次數也不超過判定樹的深度。即為：
           
　　二分求得的最壞表現和平均表現相當接近。

6、二分查找的優點和缺點
　　雖然二分查找的效率高，但是要將表按關鍵字排序。而排序本身是一種很費時的運算。既使採用高效率的排序方法也要花費O(nlgn)的時間。
　　二分查找只適用順序儲存結構。要保持表格的有序性，在順序結構中插入和刪除都必須移動大量的結點。因此，二分查找特別適用於那種一經建立就很少改動、而又經常需要查找的線性表。
　　對那些查找少而又經常需要改動的線性表，可採用鍊錶作存儲結構，進行順序查找。鍊錶上無法實現二分查找。

二分法排序

#include
#include
void TwoInsertSort(int array[],int n)
{
. i;
      for(i = 1;i       {
               num = array[i];         
          while( right >= left)//二分法查找插入位置
          {
              middle = (left + right ) /  /// 指向已排序的中間位置。       right = middle-1;
     else                    //　即將插入的元素應與右區間   }
          for( j = i-1;j >= left;j-- )//　後移排序碼大過R[i]的紀錄
              array[j+1] = array[j];
         

int rcmp( const int *a, const int *b)
{
 return (*a-*b);
}
void main() 
{
 int array[50];
The original array is :n");
 for( i=0; i {
  array[i] = 50-i;
  printf("array printf("array printf("array printf("array printf("array printf("array printf("array %dn", i, array[i]);
 }
 TwoInsertSort(array,sizeof(array)/sizeof(int));//二分法排序
 printf("nAfter sorted :n");
二分法排序
 printf("nAfter sorted :n");
二分法排序

 printf("nAfter sorted :n");

二分法排序

 printf("nAfter sorted :n");

二分法排序
 printf("nAfter sorted :n");
二分法排序

 printf("nAfter sorted :n");

二分法排名=0; i  printf("array[%d]:%dn", i, array[i]);

//函式庫函數bsearch用二分法找出一個有序數組中的一個特定數，並回傳該數的位址

 a = (int *)bsearch(&b, numarray, sizeof(numarray)/sizeof(numarray[0]), sizeof(int),rcmp);

}🎜 🎜🎜🎜🎜更多二分法查找相關文章請關注PHP中文網！ 🎜