Algorithm進(jìn)階計(jì)劃 -- 二分搜索

二分搜索

  • 二分搜索模板
  • 二分搜索運(yùn)用
圖片來(lái)源于網(wǎng)絡(luò)

1. 二分搜索模板

二分搜索(二分查找)也稱(chēng)折半查找(Binary Search)涤伐,是一種效率較高的查找方法寡壮。但是旅择,折半查找要求線(xiàn)性表必須采用順序存儲(chǔ)結(jié)構(gòu)规脸,而且表中元素按關(guān)鍵字有序排列。

二分搜索框架如下:

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

分析二分查找的一個(gè)技巧是:不要出現(xiàn) else盖溺,而是把所有情況用 else if 寫(xiě)清楚,這樣可以清楚地展現(xiàn)所有細(xì)節(jié)铣缠。

1.1 基本的二分搜索

    /**
     * 尋找一個(gè)數(shù)(基本的二分搜索)
     * <p>
     * 搜索一個(gè)數(shù)烘嘱,如果存在,返回其索引蝗蛙,否則返回 -1
     * <p>
     * 缺陷:針對(duì)如 nums = [1,2,2,2,3]拙友,target為 2 時(shí),此算法返回的索引是 2歼郭,而無(wú)法處理左側(cè)邊界索引1和右側(cè)邊界索引3
     * <p>
     * 初始化 right = nums.length - 1遗契,決定了「搜索區(qū)間」是 [left, right]
     * 決定了 while (left <= right),同時(shí)也決定了 left = mid+1 和 right = mid-1
     * <p>
     * 只需找到一個(gè) target 的索引即可病曾,當(dāng) nums[mid] == target 時(shí)可以立即返回
     */
    private int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        // [left, right]牍蜂,終止條件是 left == right + 1
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                // 直接返回
                return mid;
            } else if (nums[mid] < target) {
                // 搜索區(qū)間變?yōu)?[mid+1, right]
                left = mid + 1;
            } else if (nums[mid] > target) {
                // right = ...
                right = mid - 1;
            }
        }

        return -1;
    }

1.2 尋找左側(cè)邊界的二分搜索

    /**
     * 尋找左側(cè)邊界的二分搜索
     * <p>
     * 初始化 right = nums.length,決定了「搜索區(qū)間」是 [left, right)
     * 決定了 while (left < right)泰涂,同時(shí)也決定了 left = mid + 1 和 right = mid
     * <p>
     * 因?yàn)樾枵业?target 的最左側(cè)索引鲫竞,所以當(dāng) nums[mid] == target 時(shí)不要立即返回
     * 而要收緊右側(cè)邊界以鎖定左側(cè)邊界
     */
    private int left_bound(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0;
        int right = nums.length;

        // [left, right),終止的條件是 left == right
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                right = mid;
            } else if (nums[mid] < target) {
                // left = ...
                left = mid + 1;
            } else if (nums[mid] > target) {
                // right = ...
                right = mid;
            }
        }

        return left;
    }

當(dāng)然逼蒙,上面算法也可以使用兩邊都閉的「搜索區(qū)間」來(lái)實(shí)現(xiàn):

    /**
     * 尋找左側(cè)邊界的二分搜索  [left, right]
     */
    private int left_bound(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0;
        int right = nums.length - 1;
        // 搜索區(qū)間為 [left, right]
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                // 別返回从绘,鎖定左側(cè)邊界 (收縮右側(cè)邊界)
                right = mid - 1;
            } else if (nums[mid] < target) {
                // 搜索區(qū)間變?yōu)?[mid+1, right]
                left = mid + 1;
            } else if (nums[mid] > target) {
                // 搜索區(qū)間變?yōu)?[left, mid-1]
                right = mid - 1;
            }
        }

        // 最后要檢查 left 越界的情況
        if (left >= nums.length || nums[left] != target) return -1;
        return left;
    }

1.3 尋找右側(cè)邊界的二分搜索

    /**
     * 尋找右側(cè)邊界的二分搜索
     * <p>
     * 初始化 right = nums.length,決定了「搜索區(qū)間」是 [left, right)
     * 決定了 while (left < right)是牢,同時(shí)也決定了 left = mid + 1 和 right = mid
     * <p>
     * 需找到 target 的最右側(cè)索引僵井,當(dāng) nums[mid] == target 時(shí)不要立即返回
     * 而要收緊左側(cè)邊界以鎖定右側(cè)邊界
     * <p>
     * 又因?yàn)槭站o左側(cè)邊界時(shí)必須 left = mid + 1,所以最后無(wú)論返回 left 還是 right驳棱,必須減一
     */
    private int right_bound(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0;
        int right = nums.length;

        // [left, right)
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                // 收緊左側(cè)邊界以鎖定右側(cè)邊界
                left = mid + 1;
            } else if (nums[mid] < target) {
                // left = ...
                left = mid + 1;
            } else if (nums[mid] > target) {
                // right = ...
                right = mid;
            }
        }

        // return left - 1; // or return right - 1;
        if (left == 0) return -1;
        return nums[left-1] == target ? (left-1) : -1;
    }

同樣的批什,上面算法也可以使用兩邊都閉的「搜索區(qū)間」來(lái)實(shí)現(xiàn):

    /**
     * 尋找右側(cè)邊界的二分搜索 [left, right]
     */
    private int right_bound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                // 別返回,鎖定右側(cè)邊界 (收縮左側(cè)邊界)
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }

        // 最后要檢查 right 越界的情況
        if (right < 0 || nums[right] != target) return -1;
        return right;
    }

小結(jié):

  • 分析二分查找代碼時(shí)社搅,不要出現(xiàn) else驻债,全部展開(kāi)成 else if 方便理解。
  • 注意「搜索區(qū)間」和 while 的終止條件形葬,如果存在漏掉的元素合呐,記得在最后檢查。
  • 如需定義左閉右開(kāi)的「搜索區(qū)間」搜索左右邊界笙以,只要在 nums[mid] == target 時(shí)做修改即可淌实,搜索右側(cè)時(shí)需要減一。
  • 如果將「搜索區(qū)間」全都統(tǒng)一成兩端都閉,只要稍改 nums[mid] == target 條件處的代碼和返回的邏輯即可翩伪。

2. 二分搜索的運(yùn)用

二分搜索除了在有序數(shù)組中搜索給定的某個(gè)目標(biāo)值的索引微猖,當(dāng)搜索空間有序的時(shí)候,也可以過(guò)二分搜索「剪枝」缘屹,大幅提升效率凛剥。

2.1 愛(ài)吃香蕉的珂珂

力扣 875 題如下:

愛(ài)吃香蕉的珂珂

上面題目用暴力解法比較容易寫(xiě)出如下代碼:

    /**
     * 暴力解法
     * <p>
     * Koko 每小時(shí)最多吃一堆香蕉,如果吃不下的話(huà)留到下一小時(shí)再吃轻姿;
     * 如果吃完了這一堆還有胃口犁珠,也只會(huì)等到下一小時(shí)才會(huì)吃下一堆。
     * 在這個(gè)條件下互亮,確定珂珂吃香蕉的最小速度(根/小時(shí))
     * <p>
     * 算法要求的「H小時(shí)內(nèi)吃完香蕉的最小速度」speed犁享,顯然最少為 1,最大為 max(piles)
     */
    private int minEatingSpeed(int[] piles, int H) {
        // piles 數(shù)組的最大值
        int max = getMax(piles);
        for (int speed = 1; speed < max; speed++) {
            // 以 speed 是否能在 H 小時(shí)內(nèi)吃完香蕉
            if (canFinish(piles, speed, H)) {
                return speed;
            }
        }
        return max;
    }

值得注意的是豹休,上面的 for 循環(huán)是在連續(xù)的空間線(xiàn)性搜索炊昆,也就是二分查找可以發(fā)揮作用的標(biāo)志

尋找左側(cè)邊界的二分搜索來(lái)代替線(xiàn)性搜索威根,如下:

    /**
     * 借助二分查找技巧凤巨,算法的時(shí)間復(fù)雜度為 O(NlogN)
     */
    int minEatingSpeed(int[] piles, int H) {
        int left = 1;
        int right = getMax(piles) + 1;
        // 套用 尋找左側(cè)邊界的二分搜索 框架
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canFinish(piles, mid, H)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    /**
     * 在規(guī)定時(shí)間內(nèi)是否能吃完香蕉
     *
     * @param piles 香蕉數(shù)量
     * @param speed 吃香蕉速度
     * @param H     規(guī)定時(shí)間
     */
    boolean canFinish(int[] piles, int speed, int H) {
        int time = 0;
        for (int n : piles) {
            time += timeOf(n, speed);
        }
        return time <= H;
    }

    /**
     * 吃一堆香蕉的時(shí)間
     *
     * @param n     一堆香蕉的個(gè)數(shù)
     * @param speed 吃香蕉的速度
     */
    int timeOf(int n, int speed) {
        return (n / speed) + ((n % speed > 0) ? 1 : 0);
    }

    /**
     * 數(shù)組最大值
     */
    int getMax(int[] piles) {
        int max = 0;
        for (int n : piles) {
            max = Math.max(n, max);
        }
        return max;
    }

2.2 包裹運(yùn)輸問(wèn)題

力扣 1011 題如下:

在 D 天內(nèi)送達(dá)包裹的能力

上面題目本質(zhì)上和珂珂吃香蕉的問(wèn)題是一樣的,需要確定運(yùn)輸?shù)?strong>最小載重洛搀,假設(shè)其最小值和最大值分別為 max(weights)sum(weights)敢茁,用尋找左側(cè)邊界的二分搜索優(yōu)化線(xiàn)性搜索如下:

   /**
     * 最小載重
     */
    int shipWithDays(int[] weights, int D) {
        // 載重可能的最小值
        int left = getMax(weights);
        // 載重可能的最大值 + 1
        int right = getSum(weights) + 1;
        // 套用 尋找左側(cè)邊界的二分搜索 框架
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canFinish(weights, mid, D)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    /**
     * 若載重為 cap,是否能在 D 天內(nèi)運(yùn)完貨物留美?
     */
    boolean canFinish(int[] weights, int cap, int D) {
        int i = 0;
        for (int day = 0; day < D; day++) {
            int maxCap = cap;
            while ((maxCap -= weights[i]) >= 0) {
                i++;
                if (i == weights.length) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 數(shù)組最大值
     */
    int getMax(int[] piles) {
        int max = 0;
        for (int n : piles) {
            max = Math.max(n, max);
        }
        return max;
    }

    /**
     * 數(shù)組和
     */
    int getSum(int[] weights) {
        int sum = 0;
        for (int n : weights) {
            sum += n;
        }
        return sum;
    }

2.3 分割數(shù)組的最大值

力扣 410 題如下:

分割數(shù)組的最大值

上面題目是固定了 m 的值彰檬,讓我們確定一個(gè)最大子數(shù)組和;那可以反過(guò)來(lái)谎砾,限制一個(gè)最大子數(shù)組的和 max逢倍,來(lái)反推最大子數(shù)組的和為 max 時(shí),至少可以將 nums 分割成幾個(gè)子數(shù)組棺榔。定義函數(shù)如下:

    /**
     * 在每個(gè)子數(shù)組和不超過(guò) max 的條件下瓶堕,計(jì)算 nums 至少可以分割成幾個(gè)子數(shù)組
     *
     * 如 nums = [7,2,5,10],若 max = 10症歇,則split函數(shù)返回 3,
     * 即 nums 數(shù)組最少能分割成三個(gè)子數(shù)組谭梗,分別是[7,2],[5],[10]
     */
    int split(int[] nums, int max);

若能找到一個(gè)最小的 max 值忘晤,滿(mǎn)足上述函數(shù) split(nums, max) 的結(jié)果和 m 相等,那么這個(gè) max 值不就是符合題意的「最小的最大子數(shù)組的和」嗎激捏?

接下來(lái)對(duì) max 進(jìn)行窮舉设塔,子數(shù)組至少包含一個(gè)元素,至多包含整個(gè)數(shù)組远舅,那么最大子數(shù)組的和 max 的取值范圍是閉區(qū)間 [max(nums), sum(nums)]闰蛔,即最大元素值到整個(gè)數(shù)組和之間痕钢,如下所示:

    /**
     * 計(jì)算最大子數(shù)組的和
     */
    int splitArray(int[] nums, int m){
        int low = getMax(nums);
        int high = getSum(nums);
        for (int max = low; max <= high; max++){
            // 如果最大子數(shù)組和是 max,至少可以把 nums 分割成 n 個(gè)子數(shù)組
            int n = split(nums, max);
            // 為什么是 <= 不是 == 序六?
            // split 函數(shù)采用了貪心的策略任连,計(jì)算的是 max 限制下至少能夠?qū)?nums 分割成幾個(gè)子數(shù)組
            if (n <= m){
                return max;
            }
        }
        return -1;
    }

    /**
     * 在每個(gè)子數(shù)組和不超過(guò) max 的條件下,計(jì)算 nums 至少可以分割成幾個(gè)子數(shù)組
     *
     * 如 nums = [7,2,5,10]例诀,若 max = 10随抠,則split函數(shù)返回 3,
     * 即 nums 數(shù)組最少能分割成三個(gè)子數(shù)組繁涂,分別是[7,2],[5],[10]
     */
    int split(int[] nums, int max){
        // 至少可以分割的子數(shù)組數(shù)量
        int count = 1;
        // 記錄每個(gè)子數(shù)組的元素和
        int sum = 0;
        for (int i = 0; i< nums.length; i++){
            if (sum + nums[i] > max){
                // 如果當(dāng)前子數(shù)組和大于 max 限制拱她,則這個(gè)子數(shù)組不能再添加元素了
                count++;
                sum = nums[i];
            } else {
                // 當(dāng)前子數(shù)組和還沒(méi)達(dá)到 max 限制,還可以添加元素
                sum += nums[i];
            }
        }
        return count;
    }

    /**
     * 數(shù)組最大值
     */
    int getMax(int[] nums) {
        int max = 0;
        for (int n : nums) {
            max = Math.max(n, max);
        }
        return max;
    }

    /**
     * 數(shù)組和
     */
    int getSum(int[] nums) {
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        return sum;
    }

上面代碼是用暴力解法實(shí)現(xiàn)的扔罪,由于 split 是單調(diào)函數(shù)秉沼,且符合二分查找技巧進(jìn)行優(yōu)化的標(biāo)志,因此可用二分搜索進(jìn)行優(yōu)化矿酵。

因?yàn)樗惴ǚ祷刈钚〉哪莻€(gè) max唬复,所以用尋找左側(cè)邊界的二分搜索優(yōu)化如下:

    /**
     * 計(jì)算最大子數(shù)組的和
     * <p>
     * 假設(shè) nums 元素個(gè)數(shù)為 N,元素和為 S坏瘩,則 split 函數(shù)的復(fù)雜度為 O(N)盅抚,二分查找的復(fù)雜度為 O(logS),
     * 所以算法的總時(shí)間復(fù)雜度為 O(N*logS)
     */
    int splitArray(int[] nums, int m) {
        int left = getMax(nums);
        // 一般搜索區(qū)間是左開(kāi)右閉的倔矾,所以 right 要額外加一
        int right = getSum(nums) + 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 根據(jù)分割子數(shù)組的個(gè)數(shù)收縮搜索區(qū)間
            int n = split(nums, mid);
            if (n == m) {
                // 收縮右邊界妄均,達(dá)到搜索左邊界的目的
                right = mid;
            } else if (n < m) {
                // 最大子數(shù)組和上限高了,減小一些
                right = mid;
            } else if (n > m) {
                // 最大子數(shù)組和上限低了哪自,增加一些
                left = mid + 1;
            }
        }
        return left;
    }

    int split(int[] nums, int max) {... }
    int getMax(int[] nums) {... }
    int getSum(int[] nums) {... }

小結(jié):
二分查找在實(shí)際問(wèn)題中的應(yīng)用丰包,首先思考使用 for 循環(huán)暴力解決問(wèn)題,觀(guān)察代碼是否如下形式:

for (int i = 0; i < n; i++){
    if (isOK(i)) return answer;
}

如果是壤巷,那么就可以使用二分搜索優(yōu)化搜索空間:如果要求最小值就是搜索左側(cè)邊界的二分邑彪,如果要求最大值就用搜索右側(cè)邊界的二分。


參考鏈接:

我寫(xiě)了首詩(shī)胧华,讓你閉著眼睛也能寫(xiě)對(duì)二分搜索

如何運(yùn)用二分查找算法

二分搜索怎么用寄症?我和快手面試官進(jìn)行了深度探討

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市矩动,隨后出現(xiàn)的幾起案子有巧,更是在濱河造成了極大的恐慌,老刑警劉巖悲没,帶你破解...
    沈念sama閱讀 212,884評(píng)論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件篮迎,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)甜橱,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,755評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門(mén)逊笆,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人岂傲,你說(shuō)我怎么就攤上這事难裆。” “怎么了譬胎?”我有些...
    開(kāi)封第一講書(shū)人閱讀 158,369評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵差牛,是天一觀(guān)的道長(zhǎng)。 經(jīng)常有香客問(wèn)我堰乔,道長(zhǎng)偏化,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 56,799評(píng)論 1 285
  • 正文 為了忘掉前任镐侯,我火速辦了婚禮侦讨,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘苟翻。我一直安慰自己韵卤,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,910評(píng)論 6 386
  • 文/花漫 我一把揭開(kāi)白布崇猫。 她就那樣靜靜地躺著沈条,像睡著了一般。 火紅的嫁衣襯著肌膚如雪诅炉。 梳的紋絲不亂的頭發(fā)上蜡歹,一...
    開(kāi)封第一講書(shū)人閱讀 50,096評(píng)論 1 291
  • 那天,我揣著相機(jī)與錄音涕烧,去河邊找鬼月而。 笑死,一個(gè)胖子當(dāng)著我的面吹牛议纯,可吹牛的內(nèi)容都是我干的父款。 我是一名探鬼主播,決...
    沈念sama閱讀 39,159評(píng)論 3 411
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼瞻凤,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼憨攒!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起阀参,我...
    開(kāi)封第一講書(shū)人閱讀 37,917評(píng)論 0 268
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤浓恶,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后结笨,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,360評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,673評(píng)論 2 327
  • 正文 我和宋清朗相戀三年炕吸,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了伐憾。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,814評(píng)論 1 341
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡赫模,死狀恐怖树肃,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情瀑罗,我是刑警寧澤胸嘴,帶...
    沈念sama閱讀 34,509評(píng)論 4 334
  • 正文 年R本政府宣布,位于F島的核電站斩祭,受9級(jí)特大地震影響劣像,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜摧玫,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,156評(píng)論 3 317
  • 文/蒙蒙 一耳奕、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧诬像,春花似錦屋群、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,882評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至降狠,卻和暖如春对竣,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背喊熟。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 32,123評(píng)論 1 267
  • 我被黑心中介騙來(lái)泰國(guó)打工柏肪, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人芥牌。 一個(gè)月前我還...
    沈念sama閱讀 46,641評(píng)論 2 362
  • 正文 我出身青樓烦味,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親壁拉。 傳聞我的和親對(duì)象是個(gè)殘疾皇子谬俄,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,728評(píng)論 2 351

推薦閱讀更多精彩內(nèi)容