二分查找是查找算法裡家喻戶曉的算法了，其時間復雜度為O(logn)，可是如果真的讓你立馬拿出筆寫一個二分查找的函數出來，你確定你可以比較快的完全寫對嗎？
我們的目的是從一個已經按從小到大的順序排序好的數組arr中查找值為value的元素的位置。
大體思路我們應該都很清楚：有三個游標，一個low在頭，一個high在尾，還有一個mid指向中間，如果要檢索的數據value比中間的元素arr[mid]小，那麼應該在[low,mid)區間繼續查找，即將high指向mid前面那個元素（也許你可能認為是指向mid元素的位置）；如果要檢索的數據value比中間的元素arr[mid]大，那麼應該在(mid,high]區間繼續查找，即將low指向mid後面那個元素（也許你可能認為是指向mid元素的位置）。一直執行這個步驟來縮小搜索區間直到找到arr[k]==value返回k 或 low>high時返回-1表示沒找到。
其中的細節有很多是需要格外注意的。下面我就通過一個我的一段代碼來引出需要注意的地方。
typedef int DataType;
int binarySearch(const DataType arr[],const DataType value,size_t len)
{
int low = 0, high = len-1, mid;
while(low <= high) {
mid = low + ((high-low)>>1); //思考為什麼不寫作(high+low)/2;
if(value-arr[mid]<1e-6 && arr[mid]-value<1e-6)//思考為何不寫作arr[mid]!=value
return mid;
if(value<arr[mid])
high = mid-1; //如果寫作high = mid;可以嗎
else
low = mid+1; //如果寫作low = mid;可以嗎
}
return -1;
}
在看完了上面的代碼後，你有木有想到代碼中注釋部分的問題？當你第一遍寫代碼的時候真的考慮到了嗎，如果沒考慮這些會有什麼過果呢？下面讓我們來一一道來：
（1）第六行如果寫作mid = (high+low)/2;，有木有發現high+low有點蹊跷？如果你看出來了，恭喜你說明你對數據類型對應的取值范圍很了解！當DataType定義為int型時，兩個int相加，不要以為不會越界哈~另外改成移位操作同樣完成了除以2一樣的效果，但是效率卻提高了。如果用移位的話一定要記得移位運算優先級很低，所以記得加括號！！記得加括號！括號！（重要的事說三遍，哈哈）
（2）第七行說好的判等呢，為嘛寫成了區間的形式？這個嘛，就要考慮代碼可重用性，因為細心的你可能會發現，傳入的第一個參數是數組類型，什麼類型的數組？這裡暫時定義為int,那如果是float呢？double呢？判等還用==？所以這裡考慮的是普遍情況，通過將兩個數的差值在很小范圍內來表示他們相等，int時照樣適用。
（3）第10行第12行，才開始寫的時候可能會糾結是不是要減1或者加1，當然還有第五行是寫low <= high還是low < high？舉幾個讓另一種情況出現問題的例子然後你就會明白其中的奧秘了。
好了，基本上要注意主要的問題就這些了，下面給出一個用模板函數寫好的完整代碼吧！
#include<vector>
#include<iostream>
using namespace std;
//二分查找模板
template<typename T1,typename T2>
int binarySearch(const T1 &arr,const T2 &value,size_t len)
{
int low = 0, high = len-1, mid;
while(low <= high) {
mid = low + ((high-low)>>1); //思考為什麼不寫作(high+low)/2;
if(value-arr[mid]<1e-6 && arr[mid]-value<1e-6)//思考為何不寫作arr[mid]!=value
return mid;
if(value<arr[mid])
high = mid-1; //如果寫作high = mid;可以嗎
else
low = mid+1; //如果寫作low = mid;可以嗎
}
return -1;
}
int main()
{
double arr[10];
int i;
for(i=0; i<10; i++)
arr[i] = i;
for(i=-1; i<11; i++)
cout<<"the index of '"<<i<<"': "<<binarySearch(arr,i,10)<<endl;
cout<<endl;
vector<int> arr_i(arr,arr+10);
for(i=-1; i<11; i++)
cout<<"the index of '"<<i<<"': "<<binarySearch(arr_i,i,arr_i.size())<<endl;
return 0;
}
這個模板函數可以接受不同類型的數組，當然為了兼容C++ STL中的vector容器，又對參數做了小小的改進！
時間倉促，如果內容上有什麼疑問或者錯誤之處，請指出，謝謝！
Golang二分查找算法的簡單實現 http://www.linuxidc.com/Linux/2014-02/96093.htm
二分查找改進版 http://www.linuxidc.com/Linux/2013-10/91721.htm
二分查找的實現及注意事項 http://www.linuxidc.com/Linux/2013-07/87308.htm
用Python實現二分查找 http://www.linuxidc.com/Linux/2012-12/75948.htm
二分查找之Java實現 http://www.linuxidc.com/Linux/2012-05/59869.htm
Java針對數組的普通查找法和二分查找法 http://www.linuxidc.com/Linux/2012-03/57065.htm
