二分查找 (Binary Search) 是一种效率较高的查找方法，不过其对保存的数据有所要求，数据需要线性顺序存储，同时需要保证数据是有序排列的。
虽然二分查找的思路很简单，却有很多的细节问题，如整型溢出、边界的递进等等，这里详细介绍其使用方法。
简介
二分查找可以用来查找值、边界，在进行二分查找时，包括了几个比较关键的点：A) 确定搜索的范围；B) 停止搜索条件；C) 边界递进的条件。
边界确定也就是开始设置的 left 值的大小，可以是 length - 1 或者 length ，那么其对应的初始搜索空间分别为 [0, length - 1] 以及 [0, length) ，为了方便处理，在进行迭代时也会按照相同的属性进行，也就是 [left, right] 或者 [left, right) 。
计算中间值
在获取中间值得时候，采用的是 left + (right - left) / 2 而非 (left + right) / 2 ，虽然两者等价，但是前者可以防止由于整形溢出导致的计算结果错误，假设使用无符号 8bits 保存索引，范围是 [0, 255]，那么当索引是 200 和 220 时就会溢出。
(200 + 220)/2 = (420 - 255)/2 = 165/2 = 82
另外，当范围内是偶数个元素时，因为整除的原因，会选择偏左的值，例如 6 第一元素为 2 而非 3 。
查找范围
假设数组的序号从 0 开始，那么查找时有两个范围，也就是 [0, length - 1] 以及 [0, length) ，而此时也意味着结束条件有所变化，这里以 [0, length - 1] 为例，还可以参考 闭区间 的介绍。
基本搜索
当通过中值查找到了对应的目标值后，就可以直接返回结果了；但是如果目标不存在，最终实际会通过 while() 循环中的判断条件退出，这样退出条件的判断也就很关键了。
示例代码如下。
int binary_search(int *array, int length, int target)
{
int left, right, mid;
left = 0;
right = length - 1; // range [0, length - 1]
while (left <= right) { // NOTE#1 [left, right]
mid = left + (right - left) / 2;
if (array[mid] == target)
return mid;
else if (array[mid] < target)
left = mid + 1;
else if (array[mid] > target)
right = mid - 1;
}
return -1;
}
这里以如下的数组为例，假设查找的目标是 23 ，那么详细的查找过程如下。
最后一次计算的 mid=3 也就是要查找的值。
退出条件
最好是可以直接找到对应元素，但是如果没有，那么终止条件就是已经没有任何需要搜索的元素了。
使用 while (left <= right) 时，其终止条件为 left = right + 1 ，也就对应了 [right + 1, right] 区间，其中比较关键的是会比较最后一次值，也就是 right (此时 left 和 right 相等)。
以如上的示例为例，如果查找的是 25 ，那么最后一次更新时 mid=3 值不存在，而该值要小于 25 ，那么更新 left=4，此时会再查找一次，也就只有当此时才没有搜索空间。
而 while(left < right) 的终止条件是 left = right，会忽略掉比较 right 对应的值，即使值存在，那么也可能会返回不存在。当然，也可以在最后添加 return nums[left] == target ? left : -1; 进行修改，消除异常。
边界更新
上述实际上已经判断过了 mid 值是否满足条件，因为是闭区间，那么显然接下来应该从 [left, mid - 1] 或者 [mid + 1, right] 继续搜索，这也就对应的每次搜索边界的更新方式。
左边界搜索
假设存在有序数组 [1, 2, 2, 2, 3]，需要搜索 2 ，默认的二分查找返回的是 2 ，如果要得到左侧边界 (索引 1) 或者右侧边界 (索引 3) ，上述的方法是无法进行处理的。
当然可以线性查找，但是这样就无法保证二分查找对数级的复杂度了。
另外，很多语言内置的库，一般还会将左边界搜索称为 lower_bound() 。
实现
这里的关键是，在判断 array[mid] == target 满足条件后，并没有直接返回，而是执行 right = mid - 1 ，也就是更新的搜索范围，因为这里搜索的是左侧边界，所以更新后的搜索范围是 [left, mid - 1] 。
int left_bound(int *array, int length, int target)
{
int left, right, mid;
left = 0;
right = length - 1;
while (left <= right) { // [left, right]
mid = left + (right - left) / 2;
if (array[mid] == target)
right = mid - 1;
else if (array[mid] < target)
left = mid + 1;
else if (array[mid] > target)
right = mid - 1;
}
//return left; // how many items less than target.
if (left >= length || array[left] != target)
return -1;
return left;
}
如果直接返回 left 或者 right 实际的含义是，数组中小于目标元素的个数，例如 array = [2, 3, 5, 7], target = 1 返回 0 ，array = [2, 3, 5, 7], target = 8 返回 4 。
而如上的代码则判断是否存在元素。
右边界搜索
唯一特殊的是返回值为 left - 1 ，这主要与 left 的更新策略有关，使用的是 left = mid + 1 ，那么返回时就需要减去 1 。
int right_bound(int *array, int length, int target)
{
int left, right, mid;
left = 0;
right = length - 1;
while (left <= right) { // [left, right]
mid = left + (right - left) / 2;
if (array[mid] == target)
left = mid + 1;
else if (array[mid] < target)
left = mid + 1;
else if (array[mid] > target)
right = mid - 1;
}
//return right; // how many items less or equal to target.
if (right < 0 || array[right] != target)
return -1;
return right;
}
总结
边界条件或者检查范围决定了搜索范围的更新策略，而 while 循环则决定了终止的条件。