使用 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
的中間元素,我們將從二叉樹的右側開始搜尋。