3.4.3　利用二分查找法定位数组元素

古代两大经典问题“鸡兔同笼”和“物不知数”各有巧妙的解法，可见通过代数手段求解颇具技巧，程序代码使用穷举法反而更容易。虽然穷举法能够有效解决问题，但它的缺陷很明显，就是效率太低了。在某些场合，完全可以用其他算法来替代笨拙的穷举法。假设有一串顺序排列的数字，它们从小到大依次排列，然后想要找到特定数字在该队伍中的位置。倘若使用穷举法，就得从队列的第一个数字开始，一个一个比较过去，要是目标数字正好在队伍末尾，穷举法走完一整圈才能找到该数字。

考虑到待查找的数列本身是有序的，将目标数字与数列中的某个数字比较时，如果发现目标数字较大，就无须再跟之前的数字比较，因为序号靠前的数字还不如已比较的那个数字大，还用得着去跟铁定较小的数字比较吗？反之，如果发现目标数字较小，那么无须再拿它跟序号靠后的数字比较，因为那些数字更大。

为了更直观地理解前述的算法思想，来看图3-3所示的数列队伍。

图3-3　待查找的有序数列

由图3-3可见，该数列共有10个数字，且从左到右依次增大。接着准备在该数列中找到65所在的位置，光凭肉眼看很容易发现数字65在第6个，意味着穷举法需要历经6次查找才能找到65，效率显然不高。

现在打算换一种方式，首次查找时，不去比较数列的第一个数字6，而去比较数列的中间数字54，结果发现目标数字65比54要大，表示65不可能在54之前，只可能在54之后。于是第二次查找改为比较后半段数列的中间位置，也就是83，结果发现目标数字65比83小，表示65不可能在83后面，只可能在83前面。那么第3次查找又改为比较后半段数列的前半段，这个范围的数字大于54且小于83，落在该区间的只有两个数字（65和69），继续比较目标数字65与该区间的第一个数字65，发现二者相等，表示成功找到了目标数字的所处位置是第6个。

总而言之，新的查找算法总共只花了3次比较就找到了目标数字65，说明其效率优于花了6次比较的穷举法，详细的查找步骤如图3-4所示。

图3-4　对有序数列折半查找的过程

由于这种算法每次都比较指定范围的中间位置（二分之一处），因此该查找算法名叫“二分查找法”，也叫“折半查找法”。不过为什么首次查找从中间位置开始，而不是从三分之一位置开始，或者从三分之二位置开始呢？这是因为折半查找符合概率学的最佳选择，以中间位置为分割线，目标数字落在前半段的概率是二分之一，落在后半段的概率也是二分之一，说明在这两段找到目标数字的机会是均等的。在机会均等的情况下，二分法的查找开销是各种组合中最小的，好比人民币有10元钞票和5元钞票，却没有3元钞票，也没有7元钞票。

接下来，通过具体代码来演示二分查找法的实现过程。首先构建一个有顺序的整数数组，可以利用循环语句依次生成若干随机数填入数组，再调用数组工具Arrays的sort方法对数组排序。构建随机数数组的代码示例如下（完整代码见本章源码的src\com\control\BinaryChop.java）：

        int item=0;  // 随机数变量
        int[] numbers=new int[20];  // 随机数构成的数组
        // 以下生成一个包含随机整数的数组
        loop: for (int i=0; i < numbers.length; i++) {
            item=new Random().nextInt(100);  // 生成一个小于100的随机整数
            for (int j=0; j < i; j++) {  // 遍历数组进行检查，避免塞入重复数字
                if (numbers[j] == item) {  // 若已经存在该随机数，则继续第一层循环，重新生成随机数
                    i--;  // 本次循环做了无用功，取消当前的计数
                    continue loop;  // 直接继续上一级循环
                }
            }
            numbers[i]=item;  // 往数组填入新生成的随机数
        }
        Arrays.sort(numbers);  // 对整数数组排序（默认升序排列）
        for (int seq=0; seq<numbers.length; seq++){  // 遍历并打印数组中的所有数字
            System.out.println("序号="+seq+", 数字="+numbers[seq]);
        }
        System.out.println("最后生成的随机数="+item);

运行以上的随机数组构建代码，观察到如下的输出日志：

序号=0，数字=1

序号=1，数字=5

序号=2，数字=12

序号=3，数字=15

序号=4，数字=17

序号=5，数字=20

序号=6，数字=26

序号=7，数字=38

序号=8，数字=42

序号=9，数字=45

序号=10，数字=48

序号=11，数字=50

序号=12，数字=60

序号=13，数字=70

序号=14，数字=72

序号=15，数字=79

序号=16，数字=84

序号=17，数字=88

序号=18，数字=89

序号=19，数字=95

最后生成的随机数=60

然后希望在随机数组中找到目标数字60，采取二分查找的话，需要声明3个位置变量，分别是本次查找范围的开始位置、本次查找的结束位置、本次查找的中间位置，这3个变量依据含义分别命名为start、end和middle。在每次循环的查找过程中，先计算本次循环的中间位置，接着比较中间数字与目标数字的大小，再根据比较结果调整下次循环的开始位置或结束位置。一旦在第二步的比较操作中发现找到目标数字，就打印查找日志并退出循环。据此可编写如下的二分查找代码（完整代码见本章源码的src\com\control\BinaryChop.java）：

        // 下面通过二分查找法确定目标数字排在第几位
        int aim_item=item;  // 最后生成的整数
        System.out.println("准备查找的目标数字="+aim_item);
        int start=0;  // 二分查找的开始位置
        int end=numbers.length - 1;  // 二分查找的结束位置
        int middle=0;  // 开始位置与结束位置之间的中间位置
        for (int count=1, position=-1; start <= end; count++) {
            middle=(start + end) / 2;  // 折半获得中间的位置
            System.out.println("折半查找的中间数字="+numbers[middle]);
            if (numbers[middle] > aim_item) {
                // 该位置的数字比目标数字大，表示目标数字在该位置左边
                end=middle - 1;
            } else if (numbers[middle] < aim_item) {
                // 该位置的数字比目标数字小，表示目标数字在该位置右边
                start=middle + 1;
            } else {  // 找到目标数字，跳出循环
                position=middle;
                System.out.println("查找次数="+count+", 序号位置="+position);
                break;
            }
        }

把上述的查找代码添加到前面的数组构建代码末尾，重新运行修改之后的测试程序，即可观察到程序日志多出了以下的查找信息：

准备查找的目标数字=60

折半查找的中间数字=45

折半查找的中间数字=72

折半查找的中间数字=50

折半查找的中间数字=60

查找次数=4，序号位置=12

由查找日志可知，通过二分查找法找到目标数字只花了4次比较，倘若使用穷举法来查找，同一个目标数字得比较13次才能找到，无疑二分法的执行效率大大高于穷举法。