第一個二分搜索算法早在1946年就出現(xiàn)了，但是第一個完全正確的二分搜索算法直到1962年才出現(xiàn)。Bentley在他的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內(nèi)寫出完全正確的二分搜索算法。問題的關鍵在于準確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數(shù)的各種情況，其實整理后可以發(fā)現(xiàn)它的具體算法是很直觀的，我們可用C++描述如下：
template<class Type>
int BinarySearch(Type a[],const Type& x,int n)
{
int left=0;
int right=n-1;
while(left<=right){
int middle=(left+right)/2;
if (x==a[middle]) return middle;
if (x>a[middle]) left=middle+1;
else right=middle-1;
}
return -1;
}