在 JavaScript 中，搜索已排序列表中项目的最佳方法是什么？

---

在给定的问题陈述中，我们被要求找到使用 JavaScript 功能在已排序列表中搜索元素的最佳方法。当我们谈论排序任何列表或数组时，二分查找算法是数据结构中最好的方法。

什么是 JavaScript 中已排序列表中的二分查找？

让我们了解 JavaScript 中列表的工作原理。

列表是一个存储多个元素的对象。在编程中，列表是在一个屋檐下收集类似数据元素的集合。由于列表也是一个对象，它具有一些属性和方法，使在 JavaScript 中使用列表更容易。

以下是 JavaScript 中定义列表的语法：

list = [
    { day: 'Monday', reading: 3, id: 201},
    { day: 'Tuesday', reading: 5, id: 202},
    { day: 'Sunday', reading: 6, id: 405}
];

在数据结构中，二分查找是在已排序列表中搜索项目的一种非常有效的方法。二分查找基本上基于分治法。这种方法需要 O(log n) 时间，这比线性搜索更好，因为线性搜索算法需要 O(n) 时间。

二分查找可以使用迭代和递归方法实现。

我们得到了一个已排序的列表。我们的任务是借助二分查找找到列表中元素的索引。所以我们将用一个例子来理解这一点

Input array = {2, 4, 6, 8, 10, 12}
        a = 5
Output : Item found!

Input array = {2, 4, 6, 8, 10, 12}
        a = 7
Output : Item not found!

查找元素的逻辑

在 javascript 中查找已排序列表中项目的最快捷方法是使用二分查找算法。

该算法基于分治法。因此，在分治法中，我们将已排序的列表分成两半，并将搜索元素与中间项进行比较。

如果中间元素与搜索元素相似，则搜索任务完成。否则，我们检查搜索项是否小于中间元素，则搜索将继续在列表的左半部分进行。如果搜索项大于中间元素，则我们在已排序列表的剩余右半部分搜索它。如果中间元素与搜索元素相似，则搜索任务完成。否则，我们检查搜索项是否小于中间元素，则搜索将继续在列表的左半部分进行。如果搜索项大于中间元素，则我们在已排序列表的剩余右半部分搜索它。

算法

步骤 1 - 声明一个名为 itemSearch 的函数，该函数接收列表和要搜索的元素作为参数。

步骤 2 - 声明左指针和右指针变量以查找搜索元素的确切位置。

步骤 3 - 我们在步骤 1 中声明的函数基本上是一个递归函数。该函数在其内部使用 while 循环。此循环将一直运行，直到左元素小于或等于右元素。

步骤 4 - 接下来，在 while 循环之后，我们将通过添加左元素和右元素并将总和除以 2 来计算中间元素。因此，在这个步骤中，我们得到了中间元素。

步骤 5 - 需要对步骤 4 中的特定中间元素递归地执行此操作。接下来，我们将检查搜索项是否小于或大于中间项。如果它小于搜索项，则在列表的左侧查找它，否则在中间元素的右侧搜索。

步骤 6 - 现在，为了检查搜索项，我们将使用中间变量来检查中间元素的条件。如果 middleElement 小于搜索项，则将中间计数增加 1。否则，将中间计数减少 1。

步骤 7 - 这就是递归二分查找的工作方式。现在，在此步骤中，定义一个已排序的列表和搜索项，并调用该函数以获取输出。

示例

// define function for binary search
function itemSearch(list, searchItem) {
    let left = 0;
    let right = list.length - 1;

    // loop for finding the element
    while (left <= right) {
      const middle = Math.floor((left + right) / 2);
      const middleElement = list[middle];
       
      // condition for search item
      if (middleElement === searchItem) {
        return middle;
      } else if (middleElement < searchItem) {
        left = middle + 1;
      } else {
        right = middle - 1;
      }
    }
 
    return -1;
  }

  // create search list
  const searchList = [11, 13, 15, 17, 19];
  const searchingFor = 15;
 
  // calling the function
  const foundIndex = itemSearch(searchList, searchingFor);
 
  // condition for found or not found
  if (foundIndex === -1) {
    console.log("Element has not found.");
  } else {
    console.log(`Element found at index ${foundIndex}.`);
  }

输出

 Element fFound at index 2.

上述代码是在查看问题陈述时人们可以想到的非常简单的代码，但是理解了这个逻辑之后，您可以通过使其更灵活和更简单来优化其空间和时间质量。

在上面的代码中，我们声明了一个函数，该函数接收列表和搜索项作为输入。然后我们一步一步地进行，首先通过获取中间元素将列表分成两半。并通过比较来搜索所需的元素。

在代码中，itemSearch 函数用于在已排序列表 [11, 13, 15, 17, 19] 中搜索数字。该函数返回 15 的索引值 2。这表明搜索项在索引 2 处找到。

时间复杂度

因此，已排序列表的长度为 n，这决定了二分查找算法的时间复杂度，它将为 O(log n)。这是因为搜索空间的大小在每次循环迭代中都会减半。作为输出，查找项目所需的搜索次数等于列表的大小。

除了输入列表的大小外，此技术还需要恒定的内存。因此，此方法的空间复杂度为 O(1)。因为算法可以通过仅保存少量变量来跟踪当前搜索空间和搜索元素的位置。

结论

这就是我们解决上述问题陈述的方法。在 JavaScript 中搜索已排序列表中元素的最简单可靠的方法是使用二分查找算法。此方法的时间复杂度为 O(log n)，空间复杂度为 O(1)。该方法不断将已排序列表分成两半，并将搜索项与中间元素进行比较。并允许它快速缩小搜索内存，直到找到搜索项不在列表中。