二分檢索又稱折半檢索，優點是比較次數少，檢索速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半檢索方法適用於不經常變動而檢索頻繁的有序列表。首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與檢索關鍵字比較，如果兩者相等，則檢索成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於檢索關鍵字，則進一步檢索前一子表，否則進一步檢索後一子表。重複以上過程，直到找到滿足條件的記錄，使檢索成功，或直到子表不存在為止，此時檢索不成功。
基本介紹
- 中文名：二分檢索
- 又稱：折半檢索
- 優點：比較次數少，檢索速度快
- 算法要求：必須採用順序存儲結構
算法要求,算法複雜度,代碼示例,
算法要求
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。
代碼示例
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]<x then begin i:=j+1; j:=trunc((j+n)/2) end; until (a[j]=x) or (i>=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 <srcArray[middle]) { high = middle - 1; }else { low = middle + 1; } } return -1; } public static void main(String[] args) { int[] src = new int[] {1, 3, 5, 7, 8, 9}; System.out.println(binarySearch(src, 3)); } }
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; }
