线性搜索和二分搜索有什么区别? [英] What is the difference between Linear search and Binary search?

问题描述

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

What is the difference between Linear search and Binary search?

推荐答案

线性搜索 外观在列表中，一次一个项目，没有跳跃.在复杂性方面，这是一个 O(n) 搜索 - 搜索列表所花费的时间以与列表相同的速度变大.

A linear search looks down a list, one item at a time, without jumping. In complexity terms this is an O(n) search - the time taken to search the list gets bigger at the same rate as the list does.

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

A binary search is when you start with the middle of a sorted list, and see whether that's greater than or less than the value you're looking for, which determines whether the value is in the first or second half of the list. Jump to the half way through the sublist, and compare again etc. This is pretty much how humans typically look up a word in a dictionary (although we use better heuristics, obviously - if you're looking for "cat" you don't start off at "M"). In complexity terms this is an O(log n) search - the number of search operations grows more slowly than the list does, because you're halving the "search space" with each operation.

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

As an example, suppose you were looking for U in an A-Z list of letters (index 0-25; we're looking for the value at index 20).

线性搜索会问:

list[0] == 'U'?号
list[1] == 'U'?号
list[2] == 'U'?号
list[3] == 'U'?号
list[4] == 'U'?号
list[5] == 'U'?号
...list[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.

二分查找会问:

比较 list[12] ('M') 和 'U':更小，往前看.(范围=13-25)
将 list[19] ('T') 与 'U' 进行比较:更小，往前看.(范围=20-25)
比较 list[22] ('W') 和 'U':更大，更早看.(范围=20-21)
比较 list[20] ('U') 和 'U':找到了！完成.

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)
• 二分搜索需要随机访问数据；线性搜索只需要顺序访问(这可能非常重要 - 这意味着线性搜索可以流式任意大小的数据)

• Binary search requires the input data to be sorted; linear search doesn't
• Binary search requires an ordering comparison; linear search only requires equality comparisons
• Binary search has complexity O(log n); linear search has complexity O(n) as discussed earlier
• Binary search requires random access to the data; linear search only requires sequential access (this can be very important - it means a linear search can stream data of arbitrary size)

这篇关于线性搜索和二分搜索有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！