第一個(gè)二分搜索算法早在1946年就出現(xiàn)了，但是第一個(gè)完全正確的二分搜索算法直到1962年才出現(xiàn)。Bentley在他的著作《Writing Correct Programs》中寫道，90%的計(jì)算機(jī)專家不能在2小時(shí)內(nèi)寫出完全正確的二分搜索算法。問題的關(guān)鍵在于準(zhǔn)確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數(shù)的各種情況，其實(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;
}