二分搜索与线性搜索
线性搜索,又称顺序搜索,是最简单的搜索算法。它通过检查列表中的每个元素在列表中搜索指定的值。二分搜索也是一种用于在排序列表中查找指定值的方法。二分搜索方法将选中的元素数量减半(在每次迭代中),减少了在列表中定位给定项的时间。
什么是线性搜索?
线性搜索是最简单的搜索方法,它依次检查列表中的每个元素,直到找到指定的元素。线性搜索方法的输入是一个序列(如数组、集合或字符串)和需要搜索的项。如果指定的项在所提供的序列中,则输出为true;如果不在所提供的序列中,则输出为false。由于此方法检查列表中的每个项,直到找到指定的项,在最坏的情况下,它将遍历列表中的所有元素,然后才找到所需的元素。线性搜索的复杂度为o(n)。因此,在搜索大型列表中的元素时,它被认为太慢了。但这非常简单,易于实现。
什么是二分查找?
二分搜索也是一种用于在排序列表中查找指定项的方法。该方法首先将搜索的元素与列表中间的元素进行比较。如果比较确定两个元素相等,则该方法停止并返回元素的位置。如果搜索的元素大于中间的元素,则只使用排序列表的下半部分再次启动该方法。如果搜索的元素小于中间的元素,则只使用排序列表的上半部分再次启动该方法。如果搜索的元素不在列表中,该方法将返回一个唯一值来指示这一点。因此,根据比较的结果,二分搜索方法将比较的元素数量减半(在每次迭代中)。因此,二进制搜索在对数时间内运行,导致o(log n)的平均情况性能。
二分搜索和线性搜索的区别是什么?
尽管线性搜索和二分搜索都是搜索方法,但它们有一些不同之处。二进制搜索操作于已排序的列表,而线性搜索也可以操作未排序的列表。排序列表的平均情况复杂度通常为n log n。线性搜索比二进位搜索简单直接。但是,线性搜索由于其o(n)平均情况的性能,对于大型列表来说太慢了。另一方面,二分搜索被认为是一种更有效的方法,可以用于大型列表。但是实现二进制搜索可能相当棘手,一项研究表明,精确的二进制搜索代码只能在20本书中找到5本。
留下一个回复