JavaScript 中的計算機科學：二分搜索
不久前，我發布了關於在 JavaScript 中創建二叉搜索樹的文章（第 1 部分，第 2 部分）。二叉搜索樹是一個以有序方式存儲數據的好地方，可以輕鬆搜索特定信息。然而，二叉搜索樹並不是二叉搜索有用的唯一地方。您可以對任何有序數據集使用二分搜索來執行更有效的數據搜索。
二分搜索算法
作為快速重新介紹，二分搜索算法通過評估集合中的值並確定它是否等於、小於或大於您正在搜索的值來工作。如果要查找的值小於被檢查的值，則必須在所有小於當前值的值中繼續搜索。同樣，如果要查找的值大於選中的值，則必須在所有大於當前值的值中繼續搜索。當然，如果該值與您正在搜索的值匹配，則搜索結束。那麼基本算法可以描述為：
- 如果 currentValue 等於 value，你就完成了。
- 如果 value 小於 currentValue，則向左走。轉到第 1 步。
- 如果 value 大於 currentValue，則向右走。轉到第 1 步。
這可能過於簡單化，但基礎知識都在那裡。當找不到指定的值時，您會不斷地限制搜索區域。您不是在所有位置進行搜索，而是在知道數據是有序的基礎上縮小可能性。
搜索數組
由於可以對任何有序的數據集執行二進制搜索，因此可以對其中項目進行排序的數組執行二進制搜索是有意義的。為此，您基本上將數組視為二叉搜索樹，將過程的每個步驟分為當前值、左側路徑和右側路徑。
數組的搜索區域由兩個值定義，一個起始索引和一個停止索引（有時稱為最小值和最大值）。它們分別代表最左邊的路徑和最右邊的路徑。起始指數和終止指數用於計算中間指數，中間指數在兩個極值之間等距。在算法的每一步，都會評估數組中間索引中的值以確定下一步要做什麼。如果指定值小於當前值，則將停止索引向下調整到中間減一；如果指定值大於當前值，則起始索引向上調整為中間加一。然後通過計算新的中間並重複該過程來繼續搜索。
為了更具體，考慮一個有十個字母的數組，數字“a”到“j”，你想找到字母“i”。開始索引是0，停止索引是9，所以中間是4（通過將開始索引和停止索引相加，然後除以2並消除小數餘數得到）。檢查的第一個數組項是索引 4 中的項，其中包含字母“d”。由於“i”在“d”之後，起始索引設置為 5（比中間多一），新的中間索引變為 7（同樣，停止索引加上起始索引除以 2）。現在，檢查索引 7 中的值，即字母“h”。再一次，搜索需要向右，所以起始索引設置為 8，新的中間索引也是 8（因為 8+9/2 是 8.5，所以你消除了小數）。索引 8 中的項目實際上是字母“i”，因此搜索停止。
問題是有時您要搜索的項目不存在，在這種情況下，您需要知道何時停止。當起始索引和停止索引相同時停止，因此使中間值與每個值相同。此時，如果中間索引處的值不是您要搜索的值，則該項目不存在。在前面的示例中，搜索“z”最終會導致所有三個索引均為 9。
代碼
解釋完所有這些之後，數組的二進制搜索的實際代碼非常簡單：
//Copyright 2009 Nicholas C. Zakas. All rights reserved.
//MIT-Licensed, see source file
function binarySearch(items, value){
var startIndex = 0,
stopIndex = items.length - 1,
middle = Math.floor((stopIndex + startIndex)/2);
while(items[middle] != value && startIndex < stopIndex){
//adjust search area
if (value < items[middle]){
stopIndex = middle - 1;
} else if (value > items[middle]){
startIndex = middle + 1;
}
//recalculate middle
middle = Math.floor((stopIndex + startIndex)/2);
}
//make sure it's the right value
return (items[middle] != value) ? -1 : middle;
}
每個索引都是預先計算的，然後每次通過循環進行調整。如果找到值或開始和停止索引相等，則循環上的控制條件確保退出循環。 return 語句需要檢查是否實際找到了該值，以便返回正確的位置（根據數組搜索約定，缺失值應返回 -1）。示例用法：
var items = ["a","b","c","d","e","f","g","h","i","j"];
alert(binarySearch(items, "i")); //8
alert(binarySearch(items, "b")); //1
結論
平均而言，對排序數組進行二分搜索比線性搜索更有效（傳統的 indexOf() 實現），因為最大比較次數保持較小。二進制搜索的效率為 O(log n)，而線性搜索的效率為 O(n)。作為比較點，對包含 100,000 個項目的數組進行二分搜索最多執行 16 次比較，而在同一數組中進行線性搜索最多執行 100,000 次比較。
完整的源代碼可通過我的 GitHub 項目“JavaScript 中的計算機科學”獲得。
