每日一算法:二分搜索

二分搜索算法是一種經(jīng)典算法刊苍,它允許我們?cè)跁r(shí)間復(fù)雜度為 O(log n) 的有序數(shù)組中查找給定元素的索引。在本文中棘街,我們將回顧該算法的工作原理刮吧,并學(xué)習(xí)如何在 Javascript 中實(shí)現(xiàn)它。

一個(gè)概念性的例子

二分搜索的工作原理是連續(xù)將數(shù)組一分為二啄踊,并查看中間的數(shù)字忧设,直到找到匹配項(xiàng)(或未找到匹配項(xiàng))。假設(shè)我們有一個(gè)數(shù)組 [2, 3, 4, 6, 7, 9, 10]颠通,我們需要找到數(shù)字 7 的索引址晕。

初始數(shù)組

在二分搜索中,我們首先確定數(shù)組中的中間項(xiàng)顿锰,并將其與我們要查找的數(shù)字進(jìn)行比較谨垃。我們可以通過(guò)將數(shù)組開(kāi)頭的索引(0)與數(shù)組結(jié)尾的索引(6)相加并除以 2 來(lái)找到中間索引。換句話(huà)說(shuō)硼控,middle = (start + end) / 2 = (6 + 0) / 2 = 3刘陶。

第一遍

索引 3 處的數(shù)字是 6。我們將其與我們要查找的數(shù)字 7 進(jìn)行比較牢撼。由于 6 小于 7匙隔,我們現(xiàn)在知道 6 左側(cè)(包括)的所有項(xiàng)都小于我們要查找到的數(shù)字(這就是為什么對(duì)數(shù)組進(jìn)行排序至關(guān)重要)。

數(shù)字太低了

由于排除了所有這些數(shù)字熏版,我們現(xiàn)在可以將其視為一個(gè)新數(shù)組纷责,將開(kāi)始位置移動(dòng)到前一個(gè)中間位置的右側(cè),而結(jié)束位置仍然在數(shù)組的末尾纳决。

第二遍

我們以相同的方式計(jì)算中間索引:middle = (start + end) / 2 = (4 + 6) / 2 = 5碰逸。新中間索引處的數(shù)字是 9,現(xiàn)在大于 7阔加。因此饵史,我們知道 9 右側(cè)(包括)的所有項(xiàng)都大于我們要查找的數(shù)字。

我們重復(fù)這個(gè)過(guò)程并創(chuàng)建一個(gè)新的子數(shù)組胜榔,但這次我們的末端移動(dòng)到第 5 個(gè)索引的左側(cè)胳喷。此時(shí),我們的起點(diǎn)和終點(diǎn)索引均為 4夭织,這意味著我們的中間索引計(jì)算為:middle = (4 + 4) / 2 = 4吭露。

第三遍

我們現(xiàn)在發(fā)現(xiàn)這個(gè)數(shù)字就是我們要找的!因此尊惰,我們從算法返回索引 4讲竿。

在 JavaScript 中實(shí)現(xiàn)這個(gè)算法

通常泥兰,二分搜索函數(shù)將接收兩個(gè)輸入:排序后的數(shù)組和目標(biāo)數(shù)。通常题禀,函數(shù)的目標(biāo)是輸出目標(biāo)值的索引鞋诗,如果找不到目標(biāo)值,則輸出數(shù)字 -1迈嘹。

function binarySearch(array, target) {
  // TBD
}

通過(guò)以上的概念回顧削彬,我們可以看到,在整個(gè)算法中都有一個(gè)起點(diǎn)和終點(diǎn)秀仲。因此融痛,我們可以使用 let 初始化這些值,假設(shè)它們將發(fā)生變化:

function binarySearch(array, target) {
  let start = 0
  let end = array.length - 1
}

接下來(lái)神僵,我們將實(shí)現(xiàn)一個(gè)循環(huán)雁刷,該循環(huán)將繼續(xù)將數(shù)組切成兩半,直到找到正確的索引挑豌。循環(huán)不可能是無(wú)限的安券,所以我們需要考慮它應(yīng)該何時(shí)終止墩崩。

我們?cè)诟拍钍纠锌吹矫ビⅲ覀儾荒苡幸粋€(gè)大于結(jié)束索引的開(kāi)始索引:

function binarySearch(array, target) {
  let start = 0
  let end = array.length - 1
  while (start <= end) {
    // TBD
  }
  // 如果我們走到這一步,則表明找不到目標(biāo)元素鹦筹,返回 -1
  return -1
}

請(qǐng)注意铝阐,如果開(kāi)始索引大于結(jié)束索引,則數(shù)組中的所有項(xiàng)都已排除完铐拐,并且目標(biāo)根本不存在徘键,因此返回 -1

最后遍蟋,我們可以實(shí)現(xiàn)算法的核心邏輯:

  • 尋找中間項(xiàng)
  • 如果中間項(xiàng)等于目標(biāo)吹害,則返回索引(我們找到了!)
  • 如果中間項(xiàng)大于目標(biāo)虚青,則將結(jié)束索引移動(dòng)到中間項(xiàng)的左側(cè)
  • 如果中間項(xiàng)小于目標(biāo)它呀,則將開(kāi)始索引移動(dòng)到中間項(xiàng)的右側(cè)
const binarySearch = (arr, target) => {
  let start = 0,
    end = arr.length - 1
  while (start <= end) {
    // 找到中間索引
    const middle = Math.floor((start + end) / 2)
    const guess = arr[middle]
    if (guess === target) return middle
    if (guess > target) end = middle - 1
    else start = middle + 1
  }

  return -1
}

binarySearch([1, 2, 3, 4, 5], 1) // 0
binarySearch([1, 2, 3, 4, 5], 5) // 4
binarySearch([1, 2, 3, 4, 5], 6) // -1

您可能已經(jīng)注意到我使用 Math.floor 來(lái)計(jì)算中間索引。這是因?yàn)榫哂信紨?shù)項(xiàng)的數(shù)組沒(méi)有真正的中間項(xiàng)棒厘,所以我們要確保有一個(gè)整數(shù)索引纵穿,而不是像 2.5 之類(lèi)的索引。

計(jì)算時(shí)間復(fù)雜度

我在上面提到過(guò)奢人,這個(gè)算法的時(shí)間復(fù)雜度是 O(log n)谓媒。這可以通過(guò)考慮您可能需要將任意列表長(zhǎng)度 (n) 除以 2 多少次數(shù)來(lái)計(jì)算,直到只剩下一項(xiàng)何乎。所以我們的方程是這樣的句惯,我們要求解 x土辩。

1 = n / (2^x)
2^x = n
log(2^x) = log(n)
x * log(2) = log(n)
x = log(n)

更多資料


本文首發(fā) blog,如果喜歡或者有所啟發(fā)抢野,歡迎 Star脯燃,對(duì)作者也是一種鼓勵(lì)。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末蒙保,一起剝皮案震驚了整個(gè)濱河市辕棚,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌邓厕,老刑警劉巖逝嚎,帶你破解...
    沈念sama閱讀 218,682評(píng)論 6 507
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異详恼,居然都是意外死亡补君,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,277評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門(mén)昧互,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)挽铁,“玉大人,你說(shuō)我怎么就攤上這事敞掘∵淳颍” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 165,083評(píng)論 0 355
  • 文/不壞的土叔 我叫張陵玖雁,是天一觀的道長(zhǎng)更扁。 經(jīng)常有香客問(wèn)我,道長(zhǎng)赫冬,這世上最難降的妖魔是什么浓镜? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 58,763評(píng)論 1 295
  • 正文 為了忘掉前任,我火速辦了婚禮劲厌,結(jié)果婚禮上膛薛,老公的妹妹穿的比我還像新娘。我一直安慰自己补鼻,他們只是感情好哄啄,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,785評(píng)論 6 392
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著辽幌,像睡著了一般增淹。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上乌企,一...
    開(kāi)封第一講書(shū)人閱讀 51,624評(píng)論 1 305
  • 那天虑润,我揣著相機(jī)與錄音,去河邊找鬼加酵。 笑死拳喻,一個(gè)胖子當(dāng)著我的面吹牛哭当,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播冗澈,決...
    沈念sama閱讀 40,358評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼钦勘,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了亚亲?” 一聲冷哼從身側(cè)響起彻采,我...
    開(kāi)封第一講書(shū)人閱讀 39,261評(píng)論 0 276
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎捌归,沒(méi)想到半個(gè)月后肛响,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,722評(píng)論 1 315
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡惜索,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,900評(píng)論 3 336
  • 正文 我和宋清朗相戀三年特笋,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片巾兆。...
    茶點(diǎn)故事閱讀 40,030評(píng)論 1 350
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡猎物,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出角塑,到底是詐尸還是另有隱情蔫磨,我是刑警寧澤,帶...
    沈念sama閱讀 35,737評(píng)論 5 346
  • 正文 年R本政府宣布吉拳,位于F島的核電站质帅,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏留攒。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,360評(píng)論 3 330
  • 文/蒙蒙 一嫉嘀、第九天 我趴在偏房一處隱蔽的房頂上張望炼邀。 院中可真熱鬧,春花似錦剪侮、人聲如沸拭宁。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 31,941評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)杰标。三九已至,卻和暖如春彩匕,著一層夾襖步出監(jiān)牢的瞬間腔剂,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,057評(píng)論 1 270
  • 我被黑心中介騙來(lái)泰國(guó)打工驼仪, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留掸犬,地道東北人袜漩。 一個(gè)月前我還...
    沈念sama閱讀 48,237評(píng)論 3 371
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像湾碎,于是被迫代替她去往敵國(guó)和親宙攻。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,976評(píng)論 2 355

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