java算法2_二分查找法

比如現在有個記錄名單的字典，裡面的名字是按A-Z的順序排好的，現在我想找Lily這個人。我可以從第一頁開始一頁一頁的翻，但顯然這樣效率太低了。我可以怎麼做呢？首先我直接翻到字典的中間位置，假如發現這裡是字母H開頭的，那麼由于字典順序是排好的，我就可以斷定Lily肯定在後半本書裡，前半本我就可以不看了。接着我翻到後半本書的中間，發現是字母N開頭，那麼我就可以斷定，Lily是在這後半本書的前1/2裡。依次類推，用不了幾次，我就能找到Lily了。

以上所用的就是今天要說的二分查找法，可以看出，效率比一頁一頁的翻提高了太多。但這裡我們也需要注意一點就是，我們之是以可以用這個方法查找Lily，是因為字典中的名字是排好序的，如果是亂序，用這種方法肯定就不行了。

這裡我們以一個有序的數列來介紹這個查找法：比如要查找62這個數。

[3 17 21 37 45 52 62 78 83 95]

我們記錄一個最高位95下标為9，最低位3下标為0，中間位下标=(最低位+最高位)/2取整，即為4.然後我們去中間位的數，也即下标為4對應的數45，由于45小于62，我們讓最低位=中間位+1，也就是5，這樣能重寫中間位為(5+9)/2=7,也就取得了7對應的數78，78大于62，我們讓最高位=中間位-1,也就是6，這樣重寫取中間位(5+6)/2=5，這樣又取到了52，小于62，重寫計算最低位為6，此時最高位等于最低位了，就得到了我們要的最終的值。當然如果在上一步計算的中間值正好是我們要的62，就講這個數拿出就可了。

語言顯得啰嗦且不一定能看懂，還是看代碼吧：

package com.cloud.algorithm;
public class TestBinarySearch {
    public static int binarySearch(int[] arr,int dest){
        int lower = 0;
        int upper = arr.length;
        while (lower <= upper) {
            int mid = (lower + upper) / 2;
            if (arr[mid] < dest) {
                lower = mid + 1;
            } else if (arr[mid] > dest) {
                upper = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] niArr = { 3, 17, 21, 37, 45, 52, 62, 78, 83, 95 };
        int niDestIndex = binarySearch(niArr, 62);
        if(niDestIndex==-1){
            System.out.println("沒找到");
        }else{
            System.out.println("下标為："+niDestIndex);
        }
    }
}      

package com.cloud.algorithm;
import java.util.Arrays;
public class TestArrays {
    public static void main(String[] args) {
        int[] niArr = { 78, 83, 17, 45, 52, 21, 3, 37, 62, 95 };
        // 将亂序的數組升序排列
        Arrays.sort(niArr);
        // 格式化輸出排好序的數組
        System.out.println(Arrays.toString(niArr));
        // 在指定排好序數組中按照二分查找法查找某元素的下标
        int niIndex = Arrays.binarySearch(niArr, 62);
        System.out.println("所查元素下标為："+niIndex);
    }
}