/

JavaScript演算法：二分搜尋

JavaScript演算法：二分搜尋

二分搜尋是假設要搜尋的陣列（或其他資料結構）已經排序完成。

我們從陣列和要搜尋的項目開始。

我們查看陣列的中間。我們將元素數量除以2，想像一下左邊有一部分陣列，右邊有另一部分。

如果我們的項目比正在尋找的項目小，那麼它一定在右邊的部分，因此我們可以完全捨棄右邊的部分。

然後我們執行相同的操作，將陣列的右半部分除以2，查看中間的項目，並且我們捨棄陣列的一部分。

最後，你將得到該項目（如果沒有找到該項目，將返回null）。

最後，如果陣列有8個項目，我們在最壞的情況下將在最多4步內找到該項目。

如果陣列有32個項目，在最壞的情況下我們最多需要6步。相較於線性搜尋的32步，這是一個巨大的優化！

二分搜尋的時間複雜度為O(log n)。

以下是一種可能的實現方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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值設置為只查看陣列的左半部分或右半部分，並且重複這個過程直到找到該項目。

我們返回該項目在陣列中的索引：

1
2
console.log(binarySearch([1, 2, 3, 4, 5], 1)) //0
console.log(binarySearch([1, 2, 3, 4, 5], 5)) //4

如果元素未找到，我們返回null：

1
console.log(binarySearch([1, 2, 3, 4, 5], 6)) //null

tags: [“JavaScript”, “Algorithms”, “Binary Search”, “Complexity”]