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

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

1> Jon Skeet..：

---

一个线性搜索看不起列表,每次一个项目,没有跳跃.在复杂性方面,这是一个O(n)搜索 - 搜索列表所花费的时间会以与列表相同的速率变大.

一个二进制搜索是当你有一个排序列表的中间开始,看看这是否是比你要寻找的值,它确定的值是否是列表中的第一个或第二个半大于或小于.跳到子列表的中间位置,然后再次进行比较等.这几乎是人类通常在字典中查找单词的方式(尽管我们使用更好的启发式方法,显然 - 如果你正在寻找"猫",你就不会从"M"开始).在复杂性方面,这是一种O(log n)搜索 - 搜索操作的数量比列表的增长速度慢,因为每次操作都会使"搜索空间"减半.

例如,假设您在AZ字母列表中寻找U(索引0-25;我们正在寻找索引20处的值).

线性搜索会问:

list[0] == 'U'？没有
list[1] == 'U'？没有
list[2] == 'U'？没有
list[3] == 'U'？没有
list[4] == 'U'？没有
list[5] == 'U'？不
... list[20] == 'U'？是.成品.

二进制搜索会询问:

比较list[12]('M')和'U':更小,再看看.(范围= 13-25)
比较list[19]('T')和'U':更小,再看看.(范围= 20-25)
比较list[22]('W')和'U':更大,看得更早.(范围= 20-21)
比较list[20]('U')和'U':找到它!成品.

比较两者:

二进制搜索需要对输入数据进行排序; 线性搜索没有

二进制搜索需要订购比较; 线性搜索只需要进行相等比较

二进制搜索具有复杂度O(log n); 如前所述,线性搜索具有复杂度O(n)

二进制搜索需要随机访问数据; 线性搜索只需要顺序访问(这可能非常重要 - 这意味着线性搜索可以传输任意大小的数据)

---

+1,虽然我不太喜欢你的字典类比.一个更好的类比是"猜测我在1到100场比赛中的数字"与"你得到它","太高"或"太低"的回答.

2> Mia Clarke..：

---

可以将其视为在电话簿中找到自己的方式的两种不同方式.线性搜索从头开始,读取每个名称,直到找到您要查找的内容.另一方面,二进制搜索是当你打开书本(通常在中间)时,查看页面顶部的名称,并确定你要找的名字是大于还是小于你的名字.正在寻找.如果您要查找的名称更大,那么您将继续以这种方式搜索本书的上半部分.

---

非常好的类比:用很少的单词解释它!恭喜!

3> 小智..：

---

线性搜索通过查看数据列表中的每个元素来工作,直到找到目标或到达目标为止.这导致给定列表上的O(n)性能.二进制搜索带有必须对数据进行排序的先决条件.我们可以利用这些信息来减少查找目标所需的项目数量.我们知道,如果我们查看数据中的随机项(比如中间项)并且该项大于我们的目标,那么该项右侧的所有项也将大于我们的目标.这意味着我们只需要查看数据的左侧部分.基本上,每次我们搜索目标和未命中时,我们都可以消除剩余项目的一半.这给了我们一个很好的O(log n)时间复杂度.

请记住,即使使用最有效的算法,排序数据也总是比线性搜索慢(最快的排序算法是O(n*log n)).因此,您不应该仅仅为了稍后执行单个二进制搜索而对数据进行排序.但是如果你要执行许多搜索(比如说至少是O(log n)搜索),那么对数据进行排序可能是值得的,这样你就可以执行二进制搜索.在这种情况下,您可能还会考虑其他数据结构,例如哈希表.

4> jthompson..：

---

线性搜索从值列表的开头开始,并逐个检查以查找您要查找的结果.

二进制搜索从排序数组的中间开始,并确定您要查找的值的哪一侧(如果有).然后以相同的方式再次搜索阵列的"一半",每次将结果分成两半.

5> 小智..：

---

确保考虑更快的二进制搜索的胜利是否值得保持列表排序(能够使用二进制搜索)的成本.即如果你有大量的插入/删除操作,只有偶尔的搜索,二进制搜索总共可能比线性搜索慢.