在这篇文章中，我将比较线性搜索和二分搜索算法。您将学习线性和二进制算法的伪代码，查看演示这两种方法的示例，了解时间复杂度，并获得有关如何实现算法的分步指南。
简介
作为一名程序员，您希望找到问题的最佳解决方案，以便您的代码不仅正确而且高效。选择次优算法可能意味着更长的完成时间、增加的代码复杂性，或更糟糕的是，程序崩溃。
您可能使用过搜索算法来定位数据集合中的项目。 JavaScript 语言有多种方法（例如 find）来查找数组中的项目。然而，这些方法使用线性搜索。线性搜索算法从列表的开头开始，将每个元素与搜索值进行比较，直到找到为止。
当元素数量较少时，这很好。但是，当您搜索包含数千或数百万个元素的大型列表时，您需要一种更好的方法来定位项目。这是您使用二分搜索的时候。
在本教程中，我将解释二分搜索的工作原理以及如何在 JavaScript 中实现该算法。首先，我们回顾一下线性搜索算法。
立即学习“Java免费学习笔记（深入）”；
线性搜索
我们将首先解释如何在 JavaScript 中实现线性搜索。我们将创建一个名为 linearSearch 的函数，该函数接受整数或字符串和数组作为参数。该函数将在数组中的每个元素中搜索该值，如果找到，则返回该值在数组中的位置。如果数组中没有该值，则返回-1。
线性搜索的伪代码
Set found to falseSet position to −1Set index to 0while found is false and index < number of elements if list[index] is equal to search value Set found to true Set position to index else Add 1 to indexreturn position
线性搜索的逐步说明
假设我们线性搜索的输入是 [1,9,13,16,3,4,0,12]。如果我们要搜索的值是 16，则上述逻辑将返回 3。并且，如果我们搜索 11，上述逻辑将返回 -1。让我们来分解一下。
我们通过将 found 设置为 false，将 position 设置为 -1，并将 index 设置为 0 来初始化算法。然后我们迭代：
index列表[索引]位置找到101-1false219-1false3213-1false43163true
如果我们对数组中不存在的元素遵循上述逻辑，您将看到代码返回 -1，因为 found = false，并且 position = -1 直到最后。 p>
线性搜索的Javascript实现
这是线性搜索算法的 JavaScript 实现：
function linearSearch(value, list) { let found = false; let position = -1; let index = 0; while(!found && index < list.length) { if(list[index] == value) { found = true; position = index; } else { index += 1; } } return position;}
线性搜索的属性
需要注意的是，线性搜索算法不需要使用排序列表。此外，该算法可以定制以用于不同的场景，例如通过键搜索对象数组。如果您有一个包含名字和姓氏键的客户数据数组，您可以测试该数组是否包含具有指定名字的客户。在这种情况下，您不需要检查 list[index] 是否等于我们的搜索值，而是检查 list[index].first。
线性搜索的时间复杂度
如果搜索的元素是列表中的第一个元素，则可以实现最佳情况的时间复杂度。现在，搜索只需一次比较即可完成。因此，最好情况的时间复杂度为O(1)。
如果搜索的元素是最后一个元素或者不存在于列表中，则会出现最坏情况的时间复杂度。在这种情况下，搜索必须比较数组中的所有元素。我们说输入数据的长度为 n，这意味着由于进行了 n 次比较，总体时间复杂度为 O(n)。
在上面的示例中，我在包含八个元素的数组上使用了 linearSearch 函数。在最坏的情况下，当搜索值不在列表中或位于列表末尾时，该函数将必须进行八次比较。因为我们的数组很小，所以不需要使用不同的算法进行优化。然而，超过某一点，使用线性搜索算法就不再有效，这时使用二分搜索算法会更好。
线性搜索的平均时间复杂度也是O(n)。
线性搜索的空间复杂度
该算法的整体空间复杂度相当于数组的大小。因此，O(n)。您不需要保留任何额外的空间来完成此算法。
二分查找
假设您正在玩一个猜数字游戏。系统会要求您猜测 1 到 100 之间的一个数字。如果您的数字过高或过低，您将会得到提示。
您的策略是什么？你会随机选择数字吗？您会从 1 开始，然后是 2，依此类推，直到您猜对为止？即使您有无限的猜测，您也希望在尽可能少的尝试中做出正确的猜测。因此，您可以从猜测 50 开始。如果数字较大，您可以猜测 75。如果数字较小，则意味着数字在 50 到 75 之间，您会选择中间的数字。你会继续这样，直到得到正确的数字。这类似于二分搜索的工作原理。
有两种实现二分查找的方法：
迭代法递归方法
迭代二分搜索的伪代码
下面是一些使用迭代方法表达二分搜索的伪代码：
do until the low and high pointers have not met or crossed mid = (low + high)/2 if (x == arr[mid]) return mid else if (x > arr[mid]) low = mid + 1 else high = mid - 1
递归二分搜索的伪代码
这是使用递归方法实现二分查找的伪代码。
binarySearch(arr, x, low, high) if low > high return False else mid = (low + high) / 2 if x == arr[mid] return mid else if x > arr[mid] return binarySearch(arr, x, mid + 1, high) else return binarySearch(arr, x, low, mid - 1)
无论使用何种技术，二分搜索算法始终使用分而治之的方法。
分步说明
让我们考虑一个数组 [1,9,13,16,3,5,0,12]，其中 searchValue 是 13。
基于VC与Matlab的混合编程实现图像的三维显示 WORD版
本文档主要讲述的是基于VC与Matlab的混合编程实现图像的三维显示；介绍了VC++与Matlab混合编程的一般实现方法，并实现对二维影像图的三维效果显示。 MATLAB既是一种直观、高效的计算机语言,同时又是一个科学计算平台。它为数据分析和数据可视化、算法和应用程序开发提供了最核心的数学和高级图形工具。希望本文档会给有需要的朋友带来帮助；感兴趣的朋友可以过来看看
9 查看详情
我们从执行二分搜索所需的排序数组开始。请注意，对数组进行排序的成本很高，但一旦完成，就可以多次有效地搜索该数组。
现在，高指针和低指针将分别设置为第一个和最后一个元素。中间指针设置为 (low - high) / 2 给出的索引。
由于 searchValue > mid，我们需要搜索数组的右侧。因此，我们将 low 指针设置为紧接在 mid 之后，并将 mid 重置为位于 low 和 high 指针之间。
同样，目标值位于数组的右侧。我们再次调整低指针和高指针。现在低和中指针是相同的。
现在，在 mid 处找到了 searchValue，这意味着我们已经到达搜索的末尾！
lowmidhigh列表[mid]1037524579366713
二分查找的Javascript实现
现在让我们用 JavaScript 编写二分搜索算法！
我们将创建一个函数 binarySearch，它接受一个值和一个数组作为参数。如果找到该值，它将返回列表中出现该值的索引。如果没有找到该值，则返回-1。这是我们用 JavaScript 编写的实现：
//note that list must be sorted for this function to workfunction binarySearch(value, list) { let low = 0; //left endpoint let high = list.length - 1; //right endpoint let position = -1; let found = false; let mid; while (found === false && low value) { //if in lower half high = mid - 1; } else { //in in upper half low = mid + 1; } } return position;}
时间复杂度
我们使用二分搜索来查找数组中的元素的主要原因之一是它的时间复杂度。在最佳情况下，二分查找的时间复杂度为O(1)。当数组中间的元素与搜索元素匹配时，就会发生这种情况。
在最坏的情况下，使用二分搜索搜索元素的时间复杂度为 O(log n) — 对于较大的 n 值，远低于 O(n)。要了解 log(n) 的增长速度比 n 慢多少，这里有一个 log(n) 典型值表.
n日志（n）11831024101,000,00019.91,000,000,000,000,000,00059.8
因此，正如您所看到的，n 越大，二分搜索相对于线性搜索的改进就越大。
对于使用二分搜索来搜索项目，平均情况时间复杂度也是O(log n)。
空间复杂度
实现二分查找的空间复杂度还是O(n)。
二分查找的属性
与线性搜索不同，二分搜索使用排序列表。这让我们可以使用“分而治之”的算法来解决问题。
结论
在本教程中，我们了解了如何实现线性搜索和二分搜索算法。线性搜索算法更简单，并且不需要排序数组。然而，使用较大的数组效率很低。在最坏的情况下，算法必须搜索所有元素进行 n 次比较（其中 n 是元素数量）。
二分查找算法则需要先对数组进行排序，并且实现起来比较复杂。然而，即使考虑到排序成本，它的效率也更高。例如，具有 10 个元素的数组对于二分搜索最多进行 4 次比较，而对于线性搜索则最多进行 10 次比较，这并不是一个很大的改进。然而，对于具有 1,000,000 个元素的数组，二分查找的最坏情况也只有 20 次比较。这相对于线性搜索来说是一个巨大的改进！
了解如何使用二分搜索不仅仅是面试问题的练习。这是一项实用技能，可以让您的代码更高效地工作。
这篇文章已根据 Divya Dev 的贡献进行了更新。 Divya 是一位拥有五年以上经验的前端开发人员。她是安娜大学的毕业生和金牌获得者。
以上就是二分查找算法的 JavaScript 实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/832116.html
微信扫一扫 
支付宝扫一扫 
