資料結構——二分查找

1、二分查找的定義

​ 二分查找也稱折半查找，它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列

​ 二分查找的基本思想是将n個元素分成大緻相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x,算法中止；如果x<a[n/2],則隻要在數組a的左半部分繼續搜尋x,如果x>a[n/2],則隻要在數組a的右半部搜尋x

算法要求：

​ 1.必須采用順序存儲結構

​ 2.必須按關鍵字大小有序排列

二分查找的圖示為：

2、二分查找算法代碼實作

​

int BinarySearch(List Tb1, ElemType K){
    ElemType left, right, mid;        //定義元素名額
    int NoFound = -1;        //定義元素K沒有被找到的傳回結果
    left = -1;        //定義初始名額值
    right = Tb1->length;
    while(left <= right){
        mid = (left + right)/2;
        if(K < Tb1->array[mid])        //如果K在array[mid]的左側
            right = mid - 1;
        else if(K > Tb1->array[mid])        //如果K在array[mid]的右側
            left = mid + 1;
        else
            return mid;        //如果K等于array[mid]
    }
    return NoFound;        //沒有找到K
}           

3、二分查找的優缺點

二分查找的算法時間複雜度為O(logN)

優點：比較次數少，查找速度快，平均性能好

缺點：要求待查表為有序表，且插入删除困難