--摘要：二分法的介绍已经很多了，但并不直观，因此此文诞生，希望批评指正。
二分查找是在有序数组中查找一个元素的算法，通过比较目标元素与数组中间元素来查找，如果目标值是中间元素则将返回中间元素位置。
如果目标元素较小，则继续查找小于中间元素部分，如果目标元素较大，则继续查找大于中间元素部分。直到查找成功并返回其位置，或查到失败返回。
例在 2，5，7，8，10，15，18，20，22，25，28中查找18，简要图示，下文有更详细分布图例：
C语言实现
函数原型：
int binary_search(int *array, int imin, int imax, int key)
/**
* return the index of key.
* return -1 when failed.
*/
int binary_search(int *array, int imin, int imax, int key)
{
int imid; if(array == NULL || imin > imax) {
return -;
} while(imin <= imax) {
imid = imin + (imax - imin) / ; //avoid integer overflow
if(array[imid] == key) {
return imid;
} else if(array[imid] > key) {
imax = imid - ;
} else {
imin = imid + ;
}
} return -;
}
需要注意:
中间元素的查找方法不能为imid = ( imin + imax ) / 2，这样可能会造成整数溢出，因此应改为imid = imin + (imax – imin) / 2。
整数溢出：两个大整数相加其结果超过寄存器能存储的最大值，结果不可知。
图解说明：
array： 2 5 7 8 10 15 18 20 22 25 28
length：11
key： 18
imax = length - 1 = 10
imin = 0
步骤1：
imid = ( imin + imax ) / 2 = (0 + 10) / 2 = 5
步骤2：
imid = ( imin + imax ) / 2 = (6 + 10) / 2 = 8 imax = imid -1 = 7
步骤3：
imid = ( imin + imax ) / 2 = (6 + 7) / 2 = 6 find 18: index is 6
