查詢演算法之二分查詢法

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

查詢演算法之二分查詢法

思想

二分查詢法的思想非常簡單,對於一個有序數列,找它中間的元素,看是否是查詢目標,如果不是,就看這個查詢目標是小於還是大於中間元素,然後在對應的區間內重複上述過程。

演算法

需要注意幾個問題:

  • while 迴圈:while 迴圈的條件應該是 left < right 還是 left <= right 呢?

    • 這可以從我們設定的左右邊界判斷出來,我們設定的 left = 0, right = n – 1,因此 [left, right] 是一個閉區間,那麼當 left = right 時,[left, right] 區間同樣滿足我們的設定,因此,這個迴圈內應該是 left <= right。
  • target 和 arr[mid] 的判斷:當 target > arr[mid] 時,是應該 left = mid 還是 left = mid 1 呢?

    • 這和在 while 中的判斷是一個思路,當 target > arr[mid] 時,target 在 [mid 1, r] 中,而非 [mid, r],因為顯然此時 mid 已經不可能等於 target 了,因此我們不需要再比較 target 和 arr[mid]。
    • 同樣地,當 target < arr[mid] 時,也是類似的判斷。
  • 迴圈不變數:left 和 right 的定義十分重要,因為在後面我們要不斷地維護這個定義,我們必須要保證是在 [left, right] 這個區間裡尋找 target,這也就是 迴圈不變數,意思就是 left 和 right 的值雖然一直在變化,但是有一個宣告 在 [left, right] 區間內尋找 target 是永遠不變的,只要我們維護住這個 迴圈不變數,那麼就可以保證我們的演算法是正確的。當然,這裡你也可以定義成 left = 0, right = n,即[left, right),那麼此時定義就發生了變化,相應地,在 while 中為了維護這個定義,我們需要把條件改成 left < right,因為當 left = right 時,顯然 [left, right)是錯誤的,後面再查詢時也要做相應的修改。
    private int binarySearch(T arr[], int n, T target) {

        int left = 0, right = n - 1; // 在 [left, right] 區間內尋找 target
        
        while (left <= right) { // 當 left = right 時,區間 [left, right] 仍然有效
            int mid = (left   right) / 2;
            if (arr[mid] == target)
                return mid;
            if (target > arr[mid])
                left = mid   1; // target 在 [mid 1, r] 中
            else
                right = mid - 1; // target 在 [left, mid - 1] 中
        }

        return -1;
    }

不知道到這裡大家有沒有發現一個 bug

因為 left 和 right 都是 int,所以當值足夠大時,在計算 mid = (left right) / 2 時可能會發生整型溢位!

因此,為了避免這個問題,我們使用減法來計算。

完全正確的二分查詢法

    public int binarySearch(T[] arr, int n, T target) {

        int left = 0, right = n - 1; // 在 [left, right] 區間內尋找 target

        while (left <= right) { // 當 left = right 時,區間 [left, right] 仍然有效
            int mid = left   (right - left) / 2;
            if (arr[mid].compareTo(target) == 0)
                return mid;
            if (target.compareTo(arr[mid]) > 0)
                left = mid   1; // target 在 [mid 1, r] 中
            else
                right = mid - 1; // target 在 [left, mid - 1] 中
        }

        return -1;
    }

測試

我們可以寫一個 Util 來幫助我們生成測試用例

ArrayUtil.java

    public static Integer[] generateSortedArray(int n) {

        assert n > 0;

        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i  ) {
            arr[i] = i;
        }

        return arr;
    }

BinarySearch.java

    public static void main(String[] args) {

        BinarySearch<Integer> bs = new BinarySearch<Integer>();
        int n = (int)Math.pow(10, 7); // 用 10,000,000 資料測試
        Integer[] data = ArrayUtil.generateSortedArray(n);

        long startTime = System.currentTimeMillis();
        for (int i = 0; i < n; i  )
            if (i != bs.binarySearch(data, n, i))
                throw new IllegalStateException("find i failed");
        long endTime = System.currentTimeMillis();

        System.out.println("Binary Search success!");
        System.out.println("Time cost: "   (endTime - startTime)   "ms");
    }

完整程式碼:github: My-Notes/algorithm(Java)/01-binarySearch/src/

相關文章

開發語言 最新文章