0
  • 聊天消息
  • 系統(tǒng)消息
  • 評(píng)論與回復(fù)
登錄后你可以
  • 下載海量資料
  • 學(xué)習(xí)在線課程
  • 觀看技術(shù)視頻
  • 寫文章/發(fā)帖/加入社區(qū)
會(huì)員中心
电子发烧友
开通电子发烧友VIP会员 尊享10大特权
海量资料免费下载
精品直播免费看
优质内容免费畅学
课程9折专享价
創(chuàng)作中心

完善資料讓更多小伙伴認(rèn)識(shí)你,還能領(lǐng)取20積分哦,立即完善>

3天內(nèi)不再提示

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

算法與數(shù)據(jù)結(jié)構(gòu) ? 來(lái)源:labuladong ? 作者:labuladong ? 2020-10-30 09:39 ? 次閱讀

讀完本文,你可以去力扣解決:410.分割數(shù)組的最大值(Hard)

經(jīng)常有讀者問(wèn)我,讀了之前的爆文二分查找框架詳解之后,二分查找的算法他寫的很溜了,但僅僅局限于在數(shù)組中搜索元素,不知道底怎么在算法題里面運(yùn)用二分查找技巧來(lái)優(yōu)化效率。

那我先說(shuō)結(jié)論,你想用二分查找技巧優(yōu)化算法,首先要把 for環(huán)形式的暴力算法寫出來(lái),如果算法中存在如下形式的 for 循環(huán):

//func(i)是i的單調(diào)函數(shù)(遞增遞減都可以) intfunc(inti); //形如這種for循環(huán)可以用二分查找技巧優(yōu)化效率 for(inti=0;i

如果func(i)函數(shù)是在i上單調(diào)的函數(shù),一定可以使用二分查找技巧優(yōu)化 for 循環(huán)。

「在i上單調(diào)的函數(shù)」是指func(i)的返回值隨著i的增加而增加,或者隨著i的增加而減小。

為什么滿足這個(gè)條件就可以使用二分查找?因?yàn)檫@個(gè)邏輯和「在有序數(shù)組中查找一個(gè)元素」是完全一樣的呀!

在有序數(shù)組nums中查找某一個(gè)數(shù)target,是不是最簡(jiǎn)單二分查找形式?我們看下普通的 for 循環(huán)遍歷算法:

//nums是一個(gè)有序數(shù)組 int[]nums; //target是要搜索的元素 inttarget; //搜索target在nums中的索引 for(inti=0;i

既然nums是有序數(shù)組,你把nums[i]看做函數(shù)調(diào)用,是不是可以理解為nums在參數(shù)i上是單調(diào)的?這是不是和之前說(shuō)的func(i)函數(shù)完全一樣?

當(dāng)然,前文二分查找框架詳解說(shuō)過(guò),二分查找算法還有搜索左側(cè)、右側(cè)邊界的變體,怎么運(yùn)用到具體算法問(wèn)題中呢?

還是注意觀察 for 循環(huán)形式,只是不一定是func(i) == target作為終止條件,可能是<=或者>=的關(guān)系,這個(gè)可以根據(jù)具體的題目意思來(lái)推斷,我們實(shí)操一下力扣第 410 題「分割數(shù)組的最大值」,難度Hard:

函數(shù)簽名如下:

intsplitArray(int[]nums,intm);

這個(gè)題目有點(diǎn)類似前文一道經(jīng)典動(dòng)態(tài)規(guī)劃題目高樓扔雞蛋,題目比較繞,又是最大值又是最小值的。

簡(jiǎn)單說(shuō),給你輸入一個(gè)數(shù)組nums和數(shù)字m,你要把nums分割成m個(gè)子數(shù)組。

肯定有不止一種分割方法,每種分割方法都會(huì)把nums分成m個(gè)子數(shù)組,這m個(gè)子數(shù)組中肯定有一個(gè)和最大的子數(shù)組對(duì)吧。

我們想要找一個(gè)分割方法,該方法分割出的最大子數(shù)組和是所有方法中最大子數(shù)組和最小的。

請(qǐng)你的算法返回這個(gè)分割方法對(duì)應(yīng)的最大子數(shù)組和。

我滴媽呀,這個(gè)題目看了就覺(jué)得 Hard,完全沒(méi)思路,這題怎么能和二分查找算法扯上關(guān)系?

說(shuō)個(gè)小插曲,快手面試有一道畫師畫畫的算法題,很難,就是以這道題為原型。當(dāng)時(shí)我沒(méi)做過(guò)這道力扣題,面試有點(diǎn)懵,不過(guò)之前文章二分查找算法運(yùn)用寫了兩道類似的比較簡(jiǎn)單的題目,外加面試官的提示,把那道題做出來(lái)了。

面試做算法題的時(shí)候,題目一般都會(huì)要求算法的時(shí)間復(fù)雜度,如果你發(fā)現(xiàn) O(NlogN) 這樣存在對(duì)數(shù)的復(fù)雜度,一般都要往二分查找的方向上靠,這也算是個(gè)小套路。

言歸正傳,如何解決這道數(shù)組分割的問(wèn)題?

首先,一個(gè)拍腦袋的思路就是用回溯算法框架暴力窮舉唄,我簡(jiǎn)單說(shuō)下思路:

你不是要我把nums分割成m個(gè)子數(shù)組,然后計(jì)算巴拉巴拉又是最大又是最小的那個(gè)最值嗎?那我把所有分割方案都窮舉出來(lái),那個(gè)最值肯定可以算出來(lái)對(duì)吧?

怎么窮舉呢?把nums分割成m個(gè)子數(shù)組,相當(dāng)于在len(nums)個(gè)元素的序列中切m - 1刀,對(duì)于每?jī)蓚€(gè)元素之間的間隙,我們都有兩種「選擇」,切一刀,或者不切。

你看,這不就是標(biāo)準(zhǔn)的回溯暴力窮舉思路嘛,我們根據(jù)窮舉結(jié)果去計(jì)算每種方案的最大子數(shù)組和,肯定可以算出答案。

但是回溯的缺點(diǎn)就是復(fù)雜度很高,我們剛才說(shuō)的思路其實(shí)就是「組合」嘛,時(shí)間復(fù)雜度就是組合公式:

時(shí)間復(fù)雜度其實(shí)是非常高的,所以回溯算法不是一個(gè)好的思路,還是得上二分查找技巧,反向思考這道題。

現(xiàn)在題目是固定了m的值,讓我們確定一個(gè)最大子數(shù)組和;所謂反向思考就是說(shuō),我們可以反過(guò)來(lái),限制一個(gè)最大子數(shù)組和max,來(lái)反推最大子數(shù)組和為max時(shí),至少可以將nums分割成幾個(gè)子數(shù)組。

比如說(shuō)我們可以寫這樣一個(gè)split函數(shù):

//在每個(gè)子數(shù)組和不超過(guò)max的條件下, //計(jì)算nums至少可以分割成幾個(gè)子數(shù)組 intsplit(int[]nums,intmax);

比如說(shuō)nums = [7,2,5,10],若限制max = 10,則split函數(shù)返回 3,即nums數(shù)組最少能分割成三個(gè)子數(shù)組,分別是[7,2],[5],[10]。

如果我們找到一個(gè)最小max值,滿足split(nums, max)和m相等,那么這個(gè)max值不就是符合題意的「最小的最大子數(shù)組和」嗎?

現(xiàn)在就簡(jiǎn)單了,我們只要對(duì)max進(jìn)行窮舉就行,那么最大子數(shù)組和max的取值范圍是什么呢?

顯然,子數(shù)組至少包含一個(gè)元素,至多包含整個(gè)數(shù)組,所以「最大」子數(shù)組和的取值范圍就是閉區(qū)間[max(nums), sum(nums)],也就是最大元素值到整個(gè)數(shù)組和之間。

那么,我們就可以寫出如下代碼:

/*主函數(shù),計(jì)算最大子數(shù)組和*/ intsplitArray(int[]nums,intm){ intlo=getMax(nums),hi=getSum(nums); for(intmax=lo;max<=?hi;?max++)?{ ????????//?如果最大子數(shù)組和是?max, ????????//?至少可以把?nums?分割成?n?個(gè)子數(shù)組 ????????int?n?=?split(nums,?max); ????????//?為什么是?<=?不是?==?? ????????if?(n?<=?m)?{ ????????????return?max; ????????} ????} ????return?-1; } /*?輔助函數(shù),若限制最大子數(shù)組和為?max, 計(jì)算?nums?至少可以被分割成幾個(gè)子數(shù)組?*/ int?split(int[]?nums,?int?max)?{ ????//?至少可以分割的子數(shù)組數(shù)量 ????int?count?=?1; ????//?記錄每個(gè)子數(shù)組的元素和 ????int?sum?=?0; ????for?(int?i?=?0;?i?max){ //如果當(dāng)前子數(shù)組和大于max限制 //則這個(gè)子數(shù)組不能再添加元素了 count++; sum=nums[i]; }else{ //當(dāng)前子數(shù)組和還沒(méi)達(dá)到max限制 //還可以添加元素 sum+=nums[i]; } } returncount; } //計(jì)算數(shù)組中的最大值 intgetMax(int[]nums){ intres=0; for(intn:nums) res=Math.max(n,res); returnres; } //計(jì)算數(shù)組元素和 intgetSum(int[]nums){ intres=0; for(intn:nums) res+=n; returnres; }

這段代碼有兩個(gè)關(guān)鍵問(wèn)題:

1、對(duì)max變量的窮舉是從lo到hi即從小到大的。

這是因?yàn)槲覀兦蟮氖恰缸畲笞訑?shù)組和」的「最小值」,且split函數(shù)的返回值有單調(diào)性,所以從小到大遍歷,第一個(gè)滿足條件的值就是「最小值」。

2、函數(shù)返回的條件是n <= m,而不是n == m。按照之前的思路,應(yīng)該n == m才對(duì)吧?

其實(shí),split函數(shù)采用了貪心的策略,計(jì)算的是max限制下至少能夠?qū)ums分割成幾個(gè)子數(shù)組。

舉個(gè)例子,輸入nums = [2,1,1], m = 3,顯然分割方法只有一種,即每個(gè)元素都認(rèn)為是一個(gè)子數(shù)組,最大子數(shù)組和為 2。

但是,我們的算法會(huì)在區(qū)間[2,4]窮舉max,當(dāng)max = 2時(shí),split會(huì)算出nums至少可以被分割成n = 2個(gè)子數(shù)組[2]和[1,1]。

當(dāng)max = 3時(shí)算出n = 2,當(dāng)max = 4時(shí)算出n = 1,顯然都是小于m = 3的。

所以我們不能用n == m而必須用n <= m來(lái)找到答案,因?yàn)槿绻隳馨裯ums分割成 2 個(gè)子數(shù)組([2],[1,1]),那么肯定也可以分割成 3 個(gè)子數(shù)組([2],[1],[1])。

好了,現(xiàn)在 for 循環(huán)的暴力算法已經(jīng)寫完了,但是無(wú)法通過(guò)力扣的判題系統(tǒng),會(huì)超時(shí)。

由于split是單調(diào)函數(shù),且符合二分查找技巧進(jìn)行優(yōu)化的標(biāo)志,所以可以試圖改造成二分查找。

那么應(yīng)該使用搜索左側(cè)邊界的二分查找,還是搜索右側(cè)邊界的二分查找呢?這個(gè)還是要看我們的算法邏輯:

intlo=getMax(nums),hi=getSum(nums); for(intmax=lo;max<=?hi;?max++)?{ ????int?n?=?split(nums,?max); ????if?(n?<=?m)?{ ????????return?max; ????} }

可能存在多個(gè)max使得split(nums, max)算出相同的n,因?yàn)槲覀兊乃惴〞?huì)返回最小的那個(gè)max,所以應(yīng)該使用搜索左側(cè)邊界的二分查找算法。

現(xiàn)在,問(wèn)題變?yōu)椋涸陂]區(qū)間[lo, hi]中搜索一個(gè)最小的max,使得split(nums, max)恰好等于m。

那么,我們就可以直接套用搜索左側(cè)邊界的二分搜索框架改寫代碼:

intsplitArray(int[]nums,intm){ //一般搜索區(qū)間是左開右閉的,所以hi要額外加一 intlo=getMax(nums),hi=getSum(nums)+1; while(lom){ //最大子數(shù)組和上限低了,增加一些 lo=mid+1; } } returnlo; } intsplit(int[]nums,intmax){/*見(jiàn)上文*/} intgetMax(int[]nums){/*見(jiàn)上文*/} intgetSum(int[]nums){/*見(jiàn)上文*/}

這段二分搜索的代碼就是標(biāo)準(zhǔn)的搜索左側(cè)邊界的代碼框架,如果不理解可以參見(jiàn)前文二分查找框架詳解,這里就不展開了。

至此,這道題就通過(guò)二分查找技巧高效解決了。假設(shè)nums元素個(gè)數(shù)為N,元素和為S,則split函數(shù)的復(fù)雜度為O(N),二分查找的復(fù)雜度為O(logS),所以算法的總時(shí)間復(fù)雜度為O(N*logS)

責(zé)任編輯:lq

聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場(chǎng)。文章及其配圖僅供工程師學(xué)習(xí)之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問(wèn)題,請(qǐng)聯(lián)系本站處理。 舉報(bào)投訴
  • 算法
    +關(guān)注

    關(guān)注

    23

    文章

    4629

    瀏覽量

    93254
  • 函數(shù)
    +關(guān)注

    關(guān)注

    3

    文章

    4345

    瀏覽量

    62910
  • 數(shù)組
    +關(guān)注

    關(guān)注

    1

    文章

    417

    瀏覽量

    26010

原文標(biāo)題:二分查找算法如何運(yùn)用?我和快手面試官進(jìn)行了深入探討…

文章出處:【微信號(hào):TheAlgorithm,微信公眾號(hào):算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。

收藏 0人收藏

    評(píng)論

    相關(guān)推薦

    DAC3482設(shè)置DACCLK時(shí),到底需要設(shè)置成和DATACLK相等還是二分之一的關(guān)系?

    =DACCLK時(shí)則可以看到報(bào)警寄存器先為不沖突,一段時(shí)間后變?yōu)?-away,再過(guò)一段時(shí)間變?yōu)?-away,再過(guò)一段時(shí)間變?yōu)閒ifo-collision,依次循環(huán),請(qǐng)問(wèn)我設(shè)置DACCLK時(shí)到底需要設(shè)置成和DATACLK相等還是二分之一的關(guān)系????求解救啊
    發(fā)表于 01-08 07:24

    通過(guò)安卓手機(jī)查找IP地址步驟

    —找到設(shè)置—點(diǎn)擊雙卡與移動(dòng)網(wǎng)絡(luò) ②點(diǎn)擊雙卡與移動(dòng)網(wǎng)絡(luò)中的高級(jí)設(shè)置 ③查看IP地址 在最下方就可以看到IP地址 方法 打開手機(jī)瀏覽器—輸入my ip address—即可查到IP地址相關(guān)信息 、如何在手機(jī)上查找公網(wǎng)IP地址 相
    的頭像 發(fā)表于 12-12 13:53 ?416次閱讀
    通過(guò)安卓手機(jī)<b class='flag-5'>查找</b>IP地址步驟

    為什么DAC7811輸出電壓是理論值的二分之一?

    為什么輸出電壓是理論值的二分之一?
    發(fā)表于 12-12 07:58

    Linux文件查找

    Linux文件查找 1.find查找概述 為什么要有文件查找,因?yàn)楹芏鄷r(shí)候我們可能會(huì)忘了某個(gè)文件所在的位置,此時(shí)就需要通過(guò)find來(lái)查找。 find命令可以根據(jù)不同的條件來(lái)進(jìn)行
    的頭像 發(fā)表于 12-03 17:09 ?342次閱讀

    【「從算法到電路—數(shù)字芯片算法的電路實(shí)現(xiàn)」閱讀體驗(yàn)】+一本介紹基礎(chǔ)硬件算法模塊實(shí)現(xiàn)的好書

    的。 第一章簡(jiǎn)介了芯片研發(fā)流程,算法和電路設(shè)計(jì),算法和芯片驗(yàn)證的關(guān)系,算法工具等第章介紹了基本的數(shù)字電路基礎(chǔ),具備基本的計(jì)算機(jī)或者數(shù)字電路教育的這部分知識(shí)應(yīng)該已經(jīng)了解了。不過(guò)一些內(nèi)容
    發(fā)表于 11-20 13:42

    AFE5818的幀時(shí)鐘FCLK不等于clkin,是它的二分頻,請(qǐng)問(wèn)是為什么?

    AFE5818的幀時(shí)鐘FCLK不等于clkin,是它的二分頻,請(qǐng)問(wèn)是為什么?
    發(fā)表于 11-18 08:34

    華納云:Chord算法如何管理節(jié)點(diǎn)間的聯(lián)系?

    finger表中查找最近的節(jié)點(diǎn)來(lái)實(shí)現(xiàn)。如果當(dāng)前節(jié)點(diǎn)的finger表中沒(méi)有直接指向目標(biāo)節(jié)點(diǎn)的條目,它會(huì)將請(qǐng)求轉(zhuǎn)發(fā)給finger表中指向的節(jié)點(diǎn),直到找到目標(biāo)節(jié)點(diǎn)。 動(dòng)態(tài)操作和故障處理: Chord算法需要
    發(fā)表于 11-08 16:03

    直流接地故障的查找程序和方法

    流饋線;先拉儲(chǔ)能、信號(hào)(公共屏)、測(cè)控,后拉保護(hù)、主變等裝置;拉開保護(hù)裝置電源后再上電前,需退相關(guān)保護(hù)裝置出口壓板。 、查找步驟 判斷接地性質(zhì) : 在直流系統(tǒng)出現(xiàn)接地的情況下,要先按照變電所絕緣監(jiān)測(cè)裝置的具體配置,通過(guò)
    的頭像 發(fā)表于 10-08 10:26 ?714次閱讀

    如何高效查找電氣故障

    在現(xiàn)代工業(yè)生產(chǎn)中,電氣系統(tǒng)的穩(wěn)定運(yùn)行對(duì)于確保生產(chǎn)安全和效率至關(guān)重要。然而,電氣故障的發(fā)生往往不可避免,因此快速準(zhǔn)確地查找并解決這些故障成為了電工和技術(shù)人員必備的技能。以下是一些高效查找電氣故障的方法
    的頭像 發(fā)表于 09-30 15:20 ?346次閱讀

    怎樣使用模擬電路實(shí)現(xiàn)信號(hào)的二分頻呢?

    請(qǐng)問(wèn)怎樣使用模擬電路實(shí)現(xiàn)信號(hào)的二分頻呢?
    發(fā)表于 09-10 08:06

    如何查找線路漏電的方法和步驟

    線路漏電是電氣設(shè)備和線路中常見(jiàn)的故障之一,它不僅會(huì)導(dǎo)致設(shè)備損壞,還可能引發(fā)火災(zāi)等安全事故。因此,查找和處理線路漏電問(wèn)題至關(guān)重要。 確定漏電類型 首先,我們需要確定漏電的類型。漏電分為兩種:一種是接地
    的頭像 發(fā)表于 08-26 09:07 ?2381次閱讀

    明治案例 | 【AI二分類】剝蒜機(jī)大蒜方向識(shí)別

    ,就有了大蒜脫皮機(jī),一鐘輕輕松松剝1斤~而在這個(gè)設(shè)備上,必然也少不了明治傳感其中的應(yīng)用,本期小明就來(lái)分享一下~應(yīng)用場(chǎng)景在自動(dòng)剝蒜機(jī)中,需要設(shè)備精準(zhǔn)判斷蒜瓣的方向,
    的頭像 發(fā)表于 07-16 08:25 ?256次閱讀
    明治案例 | 【AI<b class='flag-5'>二分</b>類】剝蒜機(jī)大蒜方向識(shí)別

    次回路多點(diǎn)接地故障查找儀裝置構(gòu)成及原理——每日了解電力知識(shí)

    今天武漢摩恩智能電氣有限公司帶大家了解一下MEZN-6000 次回路多點(diǎn)接地故障查找儀。 MEZN-6000 次回路多點(diǎn)接地故障查找儀裝置的構(gòu)成: 本裝置由分析儀、探測(cè)儀和信號(hào)采集
    的頭像 發(fā)表于 06-11 10:12 ?451次閱讀
    <b class='flag-5'>二</b>次回路多點(diǎn)接地故障<b class='flag-5'>查找</b>儀裝置構(gòu)成及原理——每日了解電力知識(shí)

    如何用C語(yǔ)言實(shí)現(xiàn)高效查找二分法)

    今天給分享一下使用C語(yǔ)言實(shí)現(xiàn)二分算法,主要包含以下幾部分內(nèi)容:二分查找算法介紹二分
    的頭像 發(fā)表于 06-04 08:04 ?1248次閱讀
    如何用C語(yǔ)言實(shí)現(xiàn)高效<b class='flag-5'>查找</b>(<b class='flag-5'>二分</b>法)

    二分頻電路總述 二分頻電路的功能實(shí)現(xiàn)

    分頻就是用同一個(gè)時(shí)鐘信號(hào)通過(guò)一定的電路結(jié)構(gòu)轉(zhuǎn)變成不同頻率的時(shí)鐘信號(hào)。
    的頭像 發(fā)表于 03-06 17:13 ?2609次閱讀
    <b class='flag-5'>二分</b>頻電路總述 <b class='flag-5'>二分</b>頻電路的功能實(shí)現(xiàn)

    電子發(fā)燒友

    中國(guó)電子工程師最喜歡的網(wǎng)站

    • 2931785位工程師會(huì)員交流學(xué)習(xí)
    • 獲取您個(gè)性化的科技前沿技術(shù)信息
    • 參加活動(dòng)獲取豐厚的禮品