迹忆客 专注技术分享

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