二分查找，一個很簡單的算法，而且是面試過程中，基本上都會面的一個算法，很多公司很多面試官都很喜歡面試這個算法，如果不好好的學習這個算法，你都不好意思去面試，信不信？不信請往下讀，仔仔細細的讀，保證看到最後，你會發現弱爆了。
基礎知識
二分查找算法是在有序數組中用到的較為頻繁的一種算法，在未接觸二分查找算法時，最通用的一種做法是，對數組進行遍歷，跟每個元素進行比較，其時間為O(n).但二分查找算法則更優，因為其查找時間為O(lgn)，譬如數組{1， 2， 3， 4， 5， 6， 7， 8， 9}，查找元素6，用二分查找的算法執行的話，其順序為：
1.第一步查找中間元素，即5，由於5<6，則6必然在5之後的數組元素中，那麼就在{6， 7， 8， 9}中查找，
2.尋找{6， 7， 8， 9}的中位數，為7，7>6，則6應該在7左邊的數組元素中，那麼只剩下6，即找到了。
二分查找算法就是不斷將數組進行對半分割，每次拿中間元素和goal進行比較。
入門級菜鳥寫的二分查找
菜鳥寫二分查找，最容易想到的就是遞歸，為什麼說這是菜鳥的寫法，因為說實話，這樣的方式，效率真的不高，首先遞歸需要佔用系統棧資源，再有就是 int mid = (low + high)/2 這個地方，效率本身不高。所以這種寫法問題一大堆，基本上入門級菜鳥都會選擇這樣寫，因為易懂、易寫；不用浪費多少腦筋就可以搞定。如果去面試，你給面試官寫了這個算法，基本上我們可以認為你是個菜鳥。
必然減分。int BinSearch(int Array[],int low,int high,int key/*要找的值*/)
{
if (low<=high)
{
int mid = (low+high)/2;
if(key == Array[mid])
return mid;
elseif(key<array>
return BinSearch(Array,low,mid-1,key);
elseif(key>Array[mid])
return BinSearch(Array,mid+1,high,key);
}
else
return -1;
}
中級菜鳥寫的二分查找
中級菜鳥寫二分的時候，會考慮到節約系統資源，加快速度，所以會考慮用循環來寫，所以代碼會比使用遞歸高效一點。
int BinSearch(int Array[],int SizeOfArray,int key/*要找的值*/)
{
int low=0,high=SizeOfArray-1;
int mid;
while (low<=high)
{
mid = (low+high)/2;
if(key==Array[mid])
return mid;
if(key<array>
high=mid-1;
if(key>Array[mid])
low=mid+1;
}
return -1;
}
神級菜鳥寫的二分查找
上面的兩種實現方式，其實仔細推敲，都是有BUG的，問題出在哪兒？
mid = (low+high)/2;
就出現在這行代碼，當我們的數組比較長的時候，low + high是會溢出的，所以有的小夥伴，可能會說既然會溢出，那麼改成：
mid = low + (high - low) >> 2
不就好了嗎？說實話，改成這樣，確實比以前好了不少；但是這樣的寫法真的就完美了嗎？既然今天我寫這篇文字，肯定要告訴你，這樣的寫法並不是完美的，因為這裡面好幾個比較、還要加法，還要移位，所以這個算法並不是很完美。
下面我貼一個我前幾天寫的二分查找；
這個代碼因為業務上的需要，寫的一個二分，首先聲明一下我的結構體：
struct Idf{
uint64_t wid;
int idf;
};
// Idf 這個結構體，保存的是一個wid，和一個idf，
idf_mmap_ptr是一個Idf的數組指針。
看完代碼，你真的學會寫二分查找了嗎？還不會的回去跪搓衣板去。
閱讀更多 波波桑 的文章
