使用 JavaScript 進行二叉搜尋

Muhammad Muzammil Hussain 2023年1月30日 2022年5月1日
  1. 通過 JavaScript 中的 Iterative 方法進行二叉搜尋
  2. 通過 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 的函式,它接受兩個引數。第一個是陣列,第二個是我們要搜尋的元素。

該函式宣告並初始化兩個變數,如 startingIndexendingIndexstartingIndex 初始化為零,因為我們想從第一個 index 迭代我們的陣列。

結束索引 使用陣列的長度進行初始化。之後,我們將建立一個 while 迴圈,該迴圈將迭代整個陣列,直到滿足條件。

這個迴圈將迭代陣列直到 startingIndex 小於或等於 endingIndex。簡單地說,它意味著沒有將要測試的陣列的非法索引。

在任何情況下,如果出現非法索引,它將終止迴圈。在這個 loop 中,首先,我們獲取陣列的 middleIndex 並取其底值。

這意味著如果 startingIndex0 並且 endingIndex9。如果我們將該值除以 2,我們將得到 4.5,這不是一個有效的索引。所以我們取它的底值,比如 5

然後我們將檢查 middleIndex's 值上是否存在 searchingElement,然後返回 true。如果沒有發生,我們將檢查我們的 searchingElement 是否小於 middleIndex 值,然後我們在左側執行搜尋。

如果我們的 searchingElement 大於給定 arraymiddleIndex,我們將從陣列的右側搜尋。如果這些情況沒有發生,那麼我們返回 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 的中間元素,我們將從二叉樹的右側開始搜尋。