二值搜索与线性搜索的区别

二分搜索与线性搜索

线性搜索，又称顺序搜索，是最简单的搜索算法。它通过检查列表中的每个元素在列表中搜索指定的值。二分搜索也是一种用于在排序列表中查找指定值的方法。二分搜索方法将选中的元素数量减半(在每次迭代中)，减少了在列表中定位给定项的时间。

什么是线性搜索?

线性搜索是最简单的搜索方法，它依次检查列表中的每个元素，直到找到指定的元素。线性搜索方法的输入是一个序列(如数组、集合或字符串)和需要搜索的项。如果指定的项在所提供的序列中，则输出为true;如果不在所提供的序列中，则输出为false。由于此方法检查列表中的每个项，直到找到指定的项，在最坏的情况下，它将遍历列表中的所有元素，然后才找到所需的元素。线性搜索的复杂度为o(n)。因此，在搜索大型列表中的元素时，它被认为太慢了。但这非常简单，易于实现。

什么是二分查找?

二分搜索也是一种用于在排序列表中查找指定项的方法。该方法首先将搜索的元素与列表中间的元素进行比较。如果比较确定两个元素相等，则该方法停止并返回元素的位置。如果搜索的元素大于中间的元素，则只使用排序列表的下半部分再次启动该方法。如果搜索的元素小于中间的元素，则只使用排序列表的上半部分再次启动该方法。如果搜索的元素不在列表中，该方法将返回一个唯一值来指示这一点。因此，根据比较的结果，二分搜索方法将比较的元素数量减半(在每次迭代中)。因此，二进制搜索在对数时间内运行，导致o(log n)的平均情况性能。

二分搜索和线性搜索的区别是什么?

尽管线性搜索和二分搜索都是搜索方法，但它们有一些不同之处。二进制搜索操作于已排序的列表，而线性搜索也可以操作未排序的列表。排序列表的平均情况复杂度通常为n log n。线性搜索比二进位搜索简单直接。但是，线性搜索由于其o(n)平均情况的性能，对于大型列表来说太慢了。另一方面，二分搜索被认为是一种更有效的方法，可以用于大型列表。但是实现二进制搜索可能相当棘手，一项研究表明，精确的二进制搜索代码只能在20本书中找到5本。