JavaScript 中的二分查找

JavaScript 中的二分查找是什么？

在 JavaScript 中，二分查找是一种用于搜索的技术，它基于分治法。借助二分查找，我们可以搜索排序数组中的任何元素。

在 JavaScript 中，二分查找将数组分成两半，直到找到元素。每一次重复，它都会消除剩下元素的一半，这使得搜索时间比线性搜索快得多。

当我们比较 二分 查找和线性查找时，二分查找要快得多，二分查找的复杂度是 O(logN)，而线性查找的时间复杂度是 O(N)。

简单来说，它是一种利用分治法进行搜索的技术，它将问题分解为更简单的问题，直到简单到可以直接解决。二分查找是一种简单、用户友好且高效的搜索算法。

JavaScript 中二分查找的实现

让我们举个例子

从下面给出的排序数组中找出 "26" 的索引。

[ 2, 6, 10, 14, 18, 22, 26, 30, 34]

让我们逐步了解如何在上述示例中应用二分查找。

1. 首先，要执行二分查找，我们需要跟踪三个变量：startIndex、middleIndex 和 endIndex。令 startIndex = 0。endIndex 始终可以通过数组计算得出。endIndex = arr.length - 1，其中 length：endIndex = arr.length - 1。
2. 通过 startIndex 和 endIndex 并除以 2，我们将得到一个初始的 middleIndex。我们可以使用 Math.floor() 或 Math.ceil() 进行向下或向上取整，但在本例中我们将向下取整：在我们的 while 循环中，let middleIndex = Math.floor((startIndex + endIndex)/2) 将是我们要存储的唯一索引变量。然后，该过程将一直持续到 while 循环终止。在我们的情况下，使用 While (startIndex >= endIndex)。
3. 现在，让我们看一下数组；我们总共有 9 个元素。我们除以 2 并使用 Math.floor() 向下取整，这将在索引 4 处选择一个 middleIndex，我们在那里找到了数字 18。现在，我们将数字 18 与我们的目标数字 26 进行比较，看看哪个更大。
4. 如果我们知道 middleIndex 的值小于 26，那么我们的目标值将位于 middleIndex 的右侧。当前 middleIndex 的值将被赋给我们的 startIndex 变量，从而有效地删除了数组的左半部分。
5. 如果我们知道 middleIndex 的值大于目标值 26，那么我们的目标值将位于 middleIndex 的左侧。然后可以将 endIndex 变量设置为当前的 middleIndex 值，从而有效地删除了数组的右半部分。
6. 现在，我们将检查 middleIndex 是否等于目标值 26。这取决于您数组的大小和目标数字，循环可能只 循环 一次或几十次。
7. 我们找到了目标数字 26，因为 middleIndex 的数字值等于我们的目标数字。最后，我们完成了二分查找。

二分查找的几种方法

在 JavaScript 中有两种二分查找的方法/方式。

• 递归方法
• 迭代方法

递归方法

1. 递归方法的基准条件是，如果起始索引大于结束索引，则返回 false。
2. 现在，计算中间索引。
3. 然后，将中间元素与数字 a 进行比较。如果它等于 a，则返回 true。
4. 如果它大于 a，则使用 ending index = middle-1 调用相同的函数并重复步骤 1。
5. 如果它小于 a，则使用 starting index = middle +1 调用相同的 函数 并重复步骤 1。

示例

输出

 
Value found!
Value not found!   

迭代方法

在这种迭代方法中，我们不使用递归，而是使用 while 循环，循环将一直运行，直到达到基准条件，即 start 大于 end。

示例

让我们举一个例子来理解使用迭代方法实现二分查找。

输出

 
Value not found!
Value found!   

二分查找的时间和空间复杂度

JavaScript 中的二分查找时间复杂度为 O(logN)；这里，N 是数组列表中存在的元素或值的数量。

但与线性查找相比，线性查找的时间复杂度为 O(N)，这就是为什么二分查找比线性查找好得多的原因。

在 JavaScript 中，二分查找对同一个原始数组执行所有操作；它不创建新数组，因此我们可以说二分查找在 O(1) 空间下工作。

在递归和迭代这两种情况下，时间复杂度都将是 O(logN)，辅助空间将是 O(1)。

二分查找的应用

• 搜索：在 JavaScript 中，二分查找用于高效地在排序数组中查找元素。
• 数据库查询：它用于快速查找数据库表中按特定键排序的记录。
• 查找最接近的匹配项：二分查找可用于在排序列表中查找最接近目标值的数值。
• 插值查找：在 JavaScript 中，二分查找可用作插值查找的起点，插值查找是一种更快的搜索算法。

二分查找的优点

高效

在 JavaScript 中，二分查找的时间复杂度为 O(log n)，这使其对于搜索大型排序数组非常高效。

实现简单

JavaScript 中的二分查找相对容易实现和理解。

多功能

在 JavaScript 中，二分查找非常通用，可用于各种应用。

可靠

二分查找可以是一个可靠的算法，如果目标元素存在于数组中，它总是会找到它。

二分查找的缺点

需要排序数组

在 JavaScript 中，二分查找仅适用于排序数组。如果数组未排序，则必须在可以使用二分查找之前对其进行排序。

不适用于未排序数据

二分查找不适用于搜索未排序数据，因为它无法有效地找到目标元素。

可能不是大型数组的最佳选择

对于非常大的数组，其他搜索算法，如插值查找或哈希表，可能更有效。