使用 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 的中间元素,我们将从二叉树的右侧开始搜索。