二分搜索算法是一種經(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ù)組中的中間項(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ù)字熏版,我們現(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)
更多資料
- Binary Search
- Binary Search 可視化二分搜索
本文首發(fā) blog,如果喜歡或者有所啟發(fā)抢野,歡迎 Star
脯燃,對(duì)作者也是一種鼓勵(lì)。