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