HOWTO · JavaScript
使用 JavaScript 進行二叉搜尋
在本文中展示了我們如何使用 JavaScript 搜尋元素，或者我們也可以將其稱為二叉搜尋方法。我們將通過示例解釋兩種方法。
本頁內容
本文將探討使用 JavaScript 二叉搜尋元素的兩種方法。
第一個是迭代方式，第二個是遞迴方式。
通過 JavaScript 中的 Iterative 方法進行二叉搜尋
let binarySearchIterativeMethod =
function(myValuesArray, searchingElement) {
let startingIndex = 0, endingIndex = myValuesArray.length - 1;
while (startingIndex <= endingIndex) {
let midIndex = Math.floor((startingIndex + endingIndex) / 2);
if (myValuesArray[midIndex] === searchingElement)
return true;
else if (myValuesArray[midIndex] < searchingElement)
startingIndex = midIndex + 1;
else
endingIndex = midIndex - 1;
}
return false;
}
let myValuesArray = [1, 3, 5, 7, 8, 9];
let searchingElement = 5;
if (binarySearchIterativeMethod(myValuesArray, searchingElement))
console.log('Element found in an Array');
else
console.log('Element not found an Array');
searchingElement = 6;
if (binarySearchIterativeMethod(myValuesArray, searchingElement))
console.log('Element found in an Array');
else
console.log('Element not found in an Array');
輸出：
For searchingElement value 5 we got
Element found in an Array
For searchingElement value 6 because its not in our array we got
Element not found in an Array
在上面的程式碼中，我們首先宣告瞭一個名為 binarySearchIterativeMethod 的函式，它接受兩個引數。第一個是陣列，第二個是我們要搜尋的元素。
該函式宣告並初始化兩個變數，如 startingIndex 和 endingIndex。startingIndex 初始化為零，因為我們想從第一個 index 迭代我們的陣列。
結束索引 使用陣列的長度進行初始化。之後，我們將建立一個 while 迴圈，該迴圈將迭代整個陣列，直到滿足條件。
這個迴圈將迭代陣列直到 startingIndex 小於或等於 endingIndex。簡單地說，它意味著沒有將要測試的陣列的非法索引。
在任何情況下，如果出現非法索引，它將終止迴圈。在這個 loop 中，首先，我們獲取陣列的 middleIndex 並取其底值。
這意味著如果 startingIndex 是 0 並且 endingIndex 是 9。如果我們將該值除以 2，我們將得到 4.5，這不是一個有效的索引。所以我們取它的底值，比如 5。
然後我們將檢查 middleIndex's 值上是否存在 searchingElement，然後返回 true。如果沒有發生，我們將檢查我們的 searchingElement 是否小於 middleIndex 值，然後我們在左側執行搜尋。
如果我們的 searchingElement 大於給定 array 的 middleIndex，我們將從陣列的右側搜尋。如果這些情況沒有發生，那麼我們返回 false。
之後，我們將建立一個 array，對其進行初始化，然後建立一個名為 searchingElement 的變數並使用值 6 對其進行初始化。
之後，我們呼叫函式 binarySearchIterativeMethod 並傳遞 array 和搜尋元素並檢查它是否該函式返回 true，我們將找到輸出值。如果一個函式沒有返回 true，我們顯示 Item is not found。
通過 JavaScript 中的遞迴方法進行二叉搜尋
let binarySearchRecursiveFunction =
function(arr, x, startIndex, endIndex) {
if (startIndex > endIndex) return false;
let middleIndex = Math.floor((startIndex + endIndex) / 2);
if (arr[middleIndex] === x) return true;
if (arr[middleIndex] > x)
return binarySearchRecursiveFunction(arr, x, startIndex, middleIndex - 1);
else
return binarySearchRecursiveFunction(arr, x, middleIndex + 1, endIndex);
}
let arr = [1, 3, 5, 7, 8, 9];
let x = 5;
if (binarySearchRecursiveFunction(arr, x, 0, arr.length - 1))
console.log('Element found in an Array');
else
console.log('Element not found in an Array');
x = 9;
if (binarySearchRecursiveFunction(arr, x, 0, arr.length - 1))
console.log('Element found in an Array');
else
console.log('Element not found in an Array');
輸出：
For searchingElement value 5 we got
Element found in an Array
For searchingElement value 9 because its not in our array we got
Element not found in an Array
在上面的函式中，我們首先檢查如果 startIndex 大於 endIndex，我們將返回 false。
然後，我們將檢查名為 x 的搜尋元素是否等於給定 array 的中間索引，然後我們將返回 true。如果搜尋元素小於中間索引，我們從 array 的左側搜尋。
如果搜尋元素大於 array 的中間元素，我們將從二叉樹的右側開始搜尋。