當前位置:成語大全網 - 新華字典 - C語言高手進,答得好加分

C語言高手進,答得好加分

二分查找又稱折半查找,它是壹種效率較高的查找方法。

二分查找要求:1.必須采用順序存儲結構

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

優缺點折半查找法的優點是比較次數少,查找速度快,平均性能好;其缺點是要求待查表為有序表,且插入刪除困難。因此,折半查找方法適用於不經常變動而查找頻繁的有序列表。

算法思想首先,將表中間位置記錄的關鍵字與查找關鍵字比較,如果兩者相等,則查找成功;否則利用中間位置記錄將表分成前、後兩個子表,如果中間位置記錄的關鍵字大於查找關鍵字,則進壹步查找前壹子表,否則進壹步查找後壹子表。

重復以上過程,直到找到滿足條件的記錄,使查找成功,或直到子表不存在為止,此時查找不成功。

算法復雜度假設其數組長度為n,其算法復雜度為o(log(n))

下面提供壹段二分查找實現的偽代碼:

BinarySearch(max,min,des)

mid-<(max+min)/2

while(min<=max)

mid=(min+max)/2

if

mid=des

then

return

mid

elseif

mid

>des

then

max=mid-1

else

min=mid+1

return

max

折半查找法也稱為二分查找法,它充分利用了元素間的次序關系,采用分治策略,可在最壞的情況下用O(log

n)完成搜索任務。它的基本思想是,將n個元素分成個數大致相同的兩半,取a[n/2]與欲查找的x作比較,如果x=a[n/2]則找到x,算法終止。如

果x<a[n/2],則我們只要在數組a的左半部繼續搜索x(這裏假設數組元素呈升序排列)。如果x>a[n/2],則我們只要在數組a的右

半部繼續搜索x。

[編輯本段]C語言代碼

int

BinSearch(SeqList

R,KeyType

K){

//在有序表R[1..n]中進行二分查找,成功時返回結點的位置,失敗時返回零

int

low=1,high=n,mid;

//置當前查找區間上、下界的初值

while(low<=high){

//當前查找區間R[low..high]非空

mid=low+((high-low)/2);//使用

(low

+

high)

/

2

會有整數溢出的問題

if(R[mid].key==K)

return

mid;

//查找成功返回

if(R[mid].key>K)

high=mid-1;

//繼續在R[low..mid-1]中查找

else

low=mid+1;

//繼續在R[mid+1..high]中查找

}

return

0;

//當low>high時表示查找區間為空,查找失敗

}

//BinSeareh