algorithm - 线性搜索和二分搜索有什么区别？

Question

线性搜索和二分搜索有什么区别？

Answer 1

A linear search查看列表，一次一个项目，不跳转。在复杂性方面，这是一个 O(n) 搜索 - 搜索列表所花费的时间以与列表相同的速度变长。

A binary search是当你从一个排序列表的中间开始，看它是大于还是小于你要查找的值，这决定了该值是在列表的前半部分还是后半部分。跳到子列表的一半，然后再次比较等。这几乎是人类通常在字典中查找单词的方式(尽管我们使用更好的启发式方法，显然 - 如果你正在寻找“猫”你不从“M”开始)。在复杂性方面，这是一个 O(log n) 搜索 - 搜索操作的数量增长比列表慢，因为每个操作都会将“搜索空间”减半。

例如，假设您要在 A-Z 字母列表(索引 0-25；我们要查找索引 20 处的值)中查找 U。

线性搜索会问:

list[0] == 'U'? No.
list[1] == 'U'? No.
list[2] == 'U'? No.
list[3] == 'U'? No.
list[4] == 'U'? No.
list[5] == 'U'? No.
... list[20] == 'U'? Yes. Finished.

二分查找会问:

Compare list[12] ('M') with 'U': Smaller, look further on. (Range=13-25)
Compare list[19] ('T') with 'U': Smaller, look further on. (Range=20-25)
Compare list[22] ('W') with 'U': Bigger, look earlier. (Range=20-21)
Compare list[20] ('U') with 'U': Found it! Finished.

两者比较:

• 二分查找需要对输入数据进行排序；线性搜索没有
• 二分查找需要排序比较；线性搜索只需要相等比较
• 二分查找的复杂度为 O(log n)；如前所述，线性搜索的复杂度为 O(n)
• 二分查找需要随机访问数据；线性搜索只需要顺序访问(这可能非常重要 - 这意味着线性搜索可以流任意大小的数据)