二分搜索又称为折半查找，用来高效快速的解决如下问题：

我们需要确定排序后的数组x[0..n-1] 中是否包含目标元素t。 说的准确一点，就是已知

n>=0且x[0]<=x[1]<=x[2]…<=x[n-1]，当n=0时数组为空，t与x中元素的数据类型相同。答案存在一个整数中，为-1则不在x数组中，否则返回具体位置0~n-1。

此问题看起来是个很小的问题，其实也不容易。据说第一篇二分搜索论文是1946年发表，但是对于完全没有错误的二分搜索程序却是在1962年才出现，用了16年的时间。可想而知，要想写出一个基本没有错误的程序不是那么简单的事儿。

下面列出此程序需要注意的地方

注意点

1. 一定要对数组进行排序

2. 如果被搜索的项不在数组中，需要返回 -1

3. 如果被搜索项多次出现，是否有特殊需求，比如需要返回第一次出现的位置

代码实现

/** * 在排序好的数组中通过二分搜索t的位置(对于t重复出现不要求找出特定位置) *  * @param a *            排序好的数组 * @param t *            被查找项 * @return */public int binarySearch(int a[], int t) { int i = 0, j = a.length - 1; int result = -1; while (i <= j) { // 取得中间值 int m = (i + j) / 2; // 被查找项大于中间值 if (t > a[m]) { // 查找 m + 1 ~ j 区间 // 注意：一定是 m + 1开始，如果是m，有可能会陷入死循环之中 i = m + 1; // 被查找项小于中间值 } else if (t < a[m]) { // 查找 i ~ m - 1 区间 // 注意：一定是 m - 1结束，如果是m，有可能会陷入死循环之中 j = m - 1; } else { // 被查找项等于中间值, 直接返回 result = m; break; } } return result; }

上面的代码是二分查找的一般形式，对于在t重复出现情况下没要求的话，完全够用了。如果需要返回第一次t出现的位置，我们又该如何写，请看下面代码：

public static int binarySearchFirstIndex(int a[], int t) { int i = 0, j = a.length - 1; int result = -1; while (i <= j) { // 取得中间值 int m = (i + j) / 2; // 被查找项大于中间值 if (t > a[m]) { // 查找 m + 1 ~ j 区间 // 注意：一定是 m + 1开始，如果是m，有可能会陷入死循环之中 i = m + 1; // 被查找项小于中间值 } else if (t < a[m]) { // 查找 i ~ m - 1 区间 // 注意：一定是 m - 1结束，如果是m，有可能会陷入死循环之中 j = m - 1; } else { // 被查找项等于中间值, 结果等于中间值 result = m; // 附加判断中间值的左边值是否等于t // 注意m > 0,如果不判断可能引起数组下表越界 if (m > 0 && t == a[m - 1]) { // 继续查找 j = m - 1; } else { break; } } } return result; }

可以看到，上面代码有一点小小的改进，会去判断中间值是否等于其左边的值，如果等于继续查找。对于查找最后一个位置，原理类似。