二分作为一种常见的算法，应用非常普遍，相信一个成熟的程序员应付一个二分的题目不成问题。不过应该大多数程序员对二分中如何处理边界的问题非常头疼（遇到二分的问题应该经常调试吧）。

我们现在仔细的研究一下，做一点理论上的东西（理论，服务于实用）。

有序数组之上

二分是建立在一个有序数组之上的，这需要一个前提条件，即元素本身是可以排序的，即元素的集合需要是一个偏序集合，集合之中的两个元素之间具有 $\le$。

通常这一步我们需要使用 sort 加上一个偏序关系（通常就是数值的大小关系，也可以自定义）。

判断函数

在尝试中值（mid）是否符合要求时，需要使用一个判断函数。

在理想情况下，这个函数的返回值可以对应到 3 种情况，即 =, <, > 。

比如我们常用的生成非递增数组的 cmp 函数：

int cmp(int a, int b){
	return a - b;
}

函数结果的 0，负，正即对应上面所说的 3 种情况。

在这种情况下，无论使用怎样的边界处理方式，都没有太大的问题。

不过，二分并不要求这个判断函数一定将返回值对应到 3 中情况，更多的是两种情况

  • $\le$ 和 > （可以用非运算进行转换）
  • $\ge$ 和 < （可以用非运算进行转换）

一个函数的返回值将对应到上面列举的两类（每类中都有两种情况）。

那么我们就需要根据这个函数的返回值是哪一类去选择使用左闭右开的区间，还是左开右闭的区间（不要再坚持一定要左开右闭了）。

如果一个判断函数的返回值对应到 $\le$ 和 > ，也就意味着可以 mid 应该被包含在下一个搜索区间中。对应的模板代码如下：


public void binarySearch()