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

我们需要确定排序后的数组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;

}

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