基本介紹
- 中文名：二分檢索法
- 外文名：binary search
- 性質：搜尋方式
- 起源地：美國
- 別名：折半檢索法
定義,代碼舉例,
定義
首先將給定值key與字典中間位置上元素的關鍵碼(key)比較，如果相等，則檢索成功；
否則，若key小，則在字典前半部分中繼續進行二分法檢索;
若key大，則在字典後半部分中繼續進行二分法檢索。
這樣，經過一次比較就縮小一半的檢索區間，如此進行下去，直到檢索成功或檢索失敗。
偶數個取中間2個其中任何一個作為中間元素
代碼舉例
java版本：
public static int BinarySearch (int[] a, int low, int high, int searchValue)
{
// recursive version
int mid;
if (high <= low)
return -1;
mid = (low + high) >>> 1; // Or mid = low + ((high - low) / 2)
if (a [mid] > searchValue)
{
return BinarySearch (a, low, mid, searchValue);
}
else if (a [mid] < searchValue)
{
return BinarySearch (a, mid + 1, high, searchValue);
}
else //when a[mid] is the search value..
{
return mid;
}
} //end function
C/C++版本：
int binary_search( int *a, int n, int key )
{
int mid, front=0, back=n-1;
while (front<=back)
{
mid = (front+back)/2;
if (a[mid]==key)
return mid;
if (a[mid]<key)
front = mid+1;
else back = mid-1;
}
return -1;
}
