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次才能找到，無疑二分法的執行效率大大高于窮舉法。