二分查找，一个很简单的算法，而且是面试过程中，基本上都会面的一个算法，很多公司很多面试官都很喜欢面试这个算法，如果不好好的学习这个算法，你都不好意思去面试，信不信？不信请往下读，仔仔细细的读，保证看到最后，你会发现弱爆了。
基础知识
二分查找算法是在有序数组中用到的较为频繁的一种算法，在未接触二分查找算法时，最通用的一种做法是，对数组进行遍历，跟每个元素进行比较，其时间为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的数组指针。
看完代码，你真的学会写二分查找了吗？还不会的回去跪搓衣板去。
閱讀更多 波波桑 的文章
