二分查找法的一些思考

分享 ? AIZero ? 于 2020-06-28 18:09:32 ? 最后回復由 青牛 2020-06-28 18:29:03 ? 661 閱讀

零基礎跟了老師一個月,思維導圖不會弄,期間學了一些算法可以做一些分享,請大家指正
查找長度:關鍵碼的比較次數,評估查找算法的性能

1. 二分查找法的一般寫法

class BinarySearch1 { // high設置為數組下標末端的后一位,即為arr.length,最后會分析原因
    public int search(int[] arr, int key, int low, int high) {
        while (low <= high) {
            int mid = (low + high) / 2;
            int midVal = arr[mid];
// 這里的判斷條件如果先是key == midVal,判斷的次數會更多,算法性能會下降
            if (key < midVal) { 
                high = mid - 1;
            }else if(midVal < key){
                low = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}

查找長度分析:每一次判斷,如果目標值在midVal左側,只需要進行一次判斷就可以轉向,但是目標值在midVal右側,需要進行兩次判斷才可以轉向。

如果將第一個條件判斷語句改為key == midVal ,則無論目標值在左側和右側都需要兩次判斷,這樣反而會降低效率。

查找長度的精確計算

我們不妨設定high與low的差值為2^k,那么數組長度為2^k-1。其中設C(k-1)總體查找長度,當進行一次二分查找時,當降維為C(k-1)時,左側每個元素少比較一次,右側每個元素少比較兩次,如果命中還需兩次比較。綜上得出如下表達式:
file
用數列不斷向下迭代,由C(1)= 2可以得出一般通式,然后除以元素個數得出每個元素被取到的平均長度
file
將n帶入得到二分查找法的時間復雜度為
file

優化的思考

  • 目標值左側轉向需要一次判斷,目標值右側轉向需要二次判斷,既然左側判斷成本低,分割點往右側移動會整體降低判斷成本。

  • 分割點的位置應該設在哪里?

2. 黃金分割查找算法(斐波那契查找算法)

分割點位置分析

對優化思路進行抽象:計算稍微有點麻煩,還可以接受
file
總體來看,黃金分割查找算法對普通的二分查找算法起到了優化效果,是在常系數上起到了作用

// 斐波那契查找算法
public class FibSearch {
    // 構造斐波那契數列,可以用動態規劃法對其優化
    public static int[] fib() {
        int[] f = new int[20];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < 20; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }
    // 實現斐波那契排序算法
    public static int fibSearch(int[] arr, int key, int low, int high) {
        int k = 0;
        int mid = 0;
        int f[] = fib();

        while (high > f[k]) {
            k++;
        }
        int[] temp = Arrays.copyOf(arr, f[k]);
        for (int i = high; i < temp.length; i++) {
            temp[i] = arr[high - 1];
        }

        while (low <= high) {
            mid = low + f[k - 1] - 1;
            if (key < temp[mid]) {    // 判斷要先判斷左側,來讓左側轉向發揮最大效用
                high = mid;        
                k--;
            } else if (key > temp[mid]) {
                low = mid + 1;
                k -= 2;
            } else {
                if (mid < high) {
                    return mid;
                } else {
                    return high - 1;
                }
            }
        }
        return -1;
    }
}

優化的思考

上面兩種查找算法比較類似快速排序分區的想法,都是如果正好找到值則立馬結束,返回下標位置,但也正是因為如此造成了查找長度的不平衡。

3. 二分查找法的優化

優化的思路

為了平衡查找長度,我們可以借鑒歸并排序的想法,直接將數組一分為二,即使能命中目標值,也不急于返回,從整體上提升性能

class BinarySearch2{
     public int search(int[] arr, int key, int low, int high) {
        while (low + 1 < high) {
            int mid = (low + high) / 2;
            int midVal = arr[mid];

            if (key < midVal) {
                high = mid;
            }else if(midVal < key){
                low = mid;
            }
        }
        return (key == arr[low])? key : -1 ;
    }
}

查找長度精確計算:與第一種方法類似,我這里直接寫結果
file
將n帶入得到二分查找法的時間復雜度為
file
綜合來看:兩種二分查找法比較來看,后者在最好的情況下不如前者,最壞的情況下優于前者,但時間復雜度整體上得到優化

優化的思考

  • 第二種二分查找法似乎已經到了優化的極限,但是二分查找的目標不僅僅在于找到,還有一個關鍵是沒找到時該返回何種數值
  • 當查找的數字不在數組中或者查找的目標個數存在多個,我們希望返回的值能為key的插入提供指導,比如key有多個,返回最后一個;key比整體小,則返回頭部的位置; key比整體大,則返回尾部的位置
  • while中的判斷方法low + 1 < high這種判斷方法對上述的情況有助力嗎?

4. 二分查找的最終優化

優化的思路

  • 數軸的表示方式,在數軸上表示數細想起來還是有挺多細節的,在整數數組中,對于一個數字2,[2,3)表示一個2,在數軸上表示為一段區間,[2,2)表示一條線,在數軸上表示2區間的前界,同時也是1區間的后界。同理[3,3)表示2區間的后界。
  • 一般都會采取前界或者一個區間來表示一個數的具體位置,但在當下這個場景并非最好的選擇。特別是碰到多個相同key元素時為后續插入位置提供位點時,只有通過后界來跳出循環才能實現。
  • 通過數字后界來返回數組能完美解決key在數組左右側,多次出現的問題,為后續的插入位置提供方向,只需在返回值+1即可。
  • high之所以選擇arr.length而不是arr.length-1,是為了服務key大于數組所有元素,保證插入位置的準確。
class BinarySearch3 {
    public int search(int[] arr, int key, int low, int high) {
        while (low < high) {
            int mid = (low + high) / 2;
            int midVal = arr[mid];

            if (key < midVal) {
                high = mid;
            }else{
                low = mid + 1;  // 代碼的核心
            }
        }
        return --low;  
    }
}

總體分析:目前是二分查找最終優化版本,在算法性能和返回值上都很不錯。

5. Java的二分查找的源碼分析

private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

源碼的分析

  1. 從時間復雜度來看,并沒有做到最優化
  2. 從意外返回值的類型來分析
    • 如果key在數組左側,返回值 -1
    • 如果key在數組右側,返回值為為負數
    • 如果存在多個key值,無法返回key最末端元素
  3. 此種返回值的好處為找到為整數,沒找到為負數,這是優勢的地方。
版權聲明:原創作品,允許轉載,轉載時務必以超鏈接的形式表明出處和作者信息。否則將追究法律責任。來自海牛部落-AIZero,http://hainiubl.com/topics/75165
本帖已被設為精華帖!
本帖由 青牛 于 4月前 加精
回復數量: 5
  • 青牛 國內首批大數據從業者,就職于金山,擔任大數據團隊核心研發工程師
    ? 2020-06-28 18:11:46

    優秀,打賞5元

  • AIZero
    ? 2020-06-28 18:16:14

    @青牛 數學表達式沒有輸出來有點可惜,數學忘了的我算了好久

  • 青牛 國內首批大數據從業者,就職于金山,擔任大數據團隊核心研發工程師
    ? 2020-06-28 18:19:06

    @AIZero 你是說發不了數學公式嗎?數學表達式你可以貼圖啊

  • AIZero
    ? 2020-06-28 18:26:52

    @青牛 在文檔里寫的能顯示,我下次會貼圖,這次的計算過程可以忽略的

  • 青牛 國內首批大數據從業者,就職于金山,擔任大數據團隊核心研發工程師
    ? 2020-06-28 18:29:03

    @AIZero 高端選手啊,都整上公式推導了。咱們這貼圖很簡單的截屏然后ctrl+V。

暫無評論~~
  • 請注意單詞拼寫,以及中英文排版,參考此頁
  • 支持 Markdown 格式, **粗體**、~~刪除線~~、`單行代碼`, 更多語法請見這里 Markdown 語法
  • 支持表情,可用Emoji的自動補全, 在輸入的時候只需要 ":" 就可以自動提示了 :metal: :point_right: 表情列表 :star: :sparkles:
  • 上傳圖片, 支持拖拽和剪切板黏貼上傳, 格式限制 - jpg, png, gif,教程
  • 發布框支持本地存儲功能,會在內容變更時保存,「提交」按鈕點擊時清空
Ctrl+Enter
上海麻将垃圾胡技巧 2633179357068657756584934191479440815097358507884587822581192661317535399832555518573730233387416 (function(){ var bp = document.createElement('script'); var curProtocol = window.location.protocol.split(':')[0]; if (curProtocol === 'https') { bp.src = 'https://zz.bdstatic.com/linksubmit/push.js'; } else { bp.src = 'http://push.zhanzhang.baidu.com/push.js'; } var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(bp, s); })();