二分檢索

二分檢索又稱折半檢索,優點是比較次數少,檢索速度快,平均性能好;其缺點是要求待查表為有序表,且插入刪除困難。首先,假設表中元素是按升序排列,將表中間位置記錄的關鍵字與檢索關鍵字比較,如果兩者相等,則檢索成功;否則利用中間位置記錄將表分成前、後兩個子表,如果中間位置記錄的關鍵字大於檢索關鍵字,則進一步檢索前一子表,否則進一步檢索後一子表。它的基本思想是,將n個元素分成個數大致相同的兩半,取a[n/2]與欲檢索的x作比較,如果x=a[n/2]則找到x,算法終止。

二分檢索

二分檢索又稱折半檢索,優點是比較次數少,檢索速度快,平均性能好;其缺點是要求待查表為有序表,且插入刪除困難。因此,折半檢索方法適用於不經常變動而檢索頻繁的有序列表。首先,假設表中元素是按升序排列,將表中間位置記錄的關鍵字與檢索關鍵字比較,如果兩者相等,則檢索成功;否則利用中間位置記錄將表分成前、後兩個子表,如果中間位置記錄的關鍵字大於檢索關鍵字,則進一步檢索前一子表,否則進一步檢索後一子表。重複以上過程,直到找到滿足條件的記錄,使檢索成功,或直到子表不存在為止,此時檢索不成功。

算法簡介

算法要求

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,算法終止。如 果xa[n/2],則我們只要在數組a的右 半部繼續搜尋x。

代碼示例

pascal原始碼

program jjzx(input,output); var a:array[1..10] of integer; i,j,n,x:integer; begin writeln('輸入10個從小到大的數:'); for i:=1 to 10 do read(a[i]); writeln('輸入要檢索的數:'); readln(x); i:=1; n:=10; j:=trunc((i+n)/2); repeat if a[j]>x then begin n:=j-1; j:=trunc((i+j)/2) end else if a[j]=n) ;{為什麼是這個結束循環條件} if a[j]=x then writeln('檢索成功!位置是:',j:3) else writeln('檢索失敗,數組中無此元素!') end.

C語言代碼

int BinSearch(SeqList * R, int n , KeyType K )

{ //在有序表R[0..n-1]中進行二分檢索,成功時返回結點的位置,失敗時返回-1

int low=0,high=n-1,mid; //置當前檢索區間上、下界的初值

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

{ return 0 ; }

while(low<=high) //當前檢索區間R[low..high]非空

{

mid=low+((high-low)/2);//使用 (low + high) / 2 會有整數溢出的問題(問題會出現在當low + high的結果大於表達式結果類型所能表示的最大值時,這樣,產生溢出後再/2是不會產生正確結果的,而low+((high-low)/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 -1; //當low>high時表示檢索區間為空,檢索失敗

} //BinSeareh

Java代碼

public class BinarySearch { /** * 二分檢索算法 * * @param srcArray 有序數組 * @param des 檢索元素 * @return des的數組下標,沒找到返回-1 */ public static int binarySearch(int[] srcArray, int des) { int low = 0; int high = srcArray.length-1; while(low <= high) { int middle = (low + high)/2; if(des == srcArray[middle]) { return middle; }else if(des

AAuto代碼

//二分檢索 function binSearch(t,v ){ var p = #t; var p2; var b = 0; do{ p2 = p; p = b + math.floor( (p-b) / 2 ) //二分折半運算 if(p==b)return; if( t[p] < v ){ //判斷下限 b = p; p = p2; } }while( t[p]>v ) //判斷上限 return t[p]==v && p; } //測試 tab = {} //創建數組,每個元素都是隨機數 for(i=1;10 ;1){ tab[i] = math.random(1, 10000) } //插入一個已知數 table.push(tab,5632) //排序 table.sort( tab) io.open() io.print( "數組",table.tostring(tab) ) io.print( "使用二分檢索,找到5632在位置:",binSearch( tab,5632 ) )

PHP代碼

function bin_sch($array, $low, $high, $k){ if ($low <= $high){ $mid = intval(($low+$high)/2); if ($array[$mid] == $k){ return $mid; }elseif ($k < $array[$mid]){ return bin_sch($array, $low, $mid-1, $k); }else{ return bin_sch($array, $mid+1, $high, $k); } } return -1; }

熱門詞條

聯絡我們