我很困惑线性搜索或二进制搜索在运行时间和存储方面是否更有效。
非常感谢详细的解释
问问题
143 次
2 回答
3
线性搜索从头开始并比较每个元素，直到找到您要查找的内容。
二进制搜索在中间拆分列表并查看您的值是大于还是小于枢轴值。然后它继续递归地这样做。
例如在人员列表中。你在找约翰。二进制搜索在列表的中间查找并可能找到 Mark。John 较低，因此搜索丢弃列表的上半部分，因为 John 不会在其中，并在下半部分重复此操作（递归）
二进制搜索效率更高，但必须对列表进行排序。
但是 - 对列表进行排序比线性搜索要慢。首先对未排序的列表进行排序不会提高效率。
于 2013-06-24T07:01:01.553 回答
3
@Trophe 涵盖了时间复杂度，所以我将尝试解释空间复杂度
空间要求具有相同的复杂性
线性搜索更简单，只需要一个变量
二分查找需要存储下限和上限，所以空间更大，但不依赖于列表的大小
所以我们说它们都是 O(1) 空间复杂度
于 2013-06-24T07:03:50.730 回答