二分搜尋是假設要搜尋的陣列(或其他資料結構)已經排序完成。
我們從陣列和要搜尋的項目開始。
我們查看陣列的中間。我們將元素數量除以2,想像一下左邊有一部分陣列,右邊有另一部分。
如果我們的項目比正在尋找的項目小,那麼它一定在右邊的部分,因此我們可以完全捨棄右邊的部分。
然後我們執行相同的操作,將陣列的右半部分除以2,查看中間的項目,並且我們捨棄陣列的一部分。
最後,你將得到該項目(如果沒有找到該項目,將返回null
)。
最後,如果陣列有8個項目,我們在最壞的情況下將在最多4步內找到該項目。
如果陣列有32個項目,在最壞的情況下我們最多需要6步。相較於線性搜尋的32步,這是一個巨大的優化!
二分搜尋的時間複雜度為O(log n)
。
以下是一種可能的實現方式:
const binarySearch = (list, item) => {
let low = 0
let high = list.length - 1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
const guess = list[mid]
if (guess === item) {
return mid
}
if (guess > item) {
high = mid - 1
} else {
low = mid + 1
}
}
return null //如果未找到
}
這如何運作?我們得到list
陣列和要搜尋的項目值。然後我們最初將low
值設置為0,並將high
值設置為陣列的最後一個索引。我們首先查看中間項目,如果它就是我們正在尋找的項目,我們將返回它,並結束。如果不是,我們將low
或high
值設置為只查看陣列的左半部分或右半部分,並且重複這個過程直到找到該項目。
我們返回該項目在陣列中的索引:
console.log(binarySearch([1, 2, 3, 4, 5], 1)) //0
console.log(binarySearch([1, 2, 3, 4, 5], 5)) //4
如果元素未找到,我們返回null
:
console.log(binarySearch([1, 2, 3, 4, 5], 6)) //null