线性搜索和二进制搜索的区别是什么？ [英] 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.

一个二进制搜索是当你开始使用的排序列表的中间，看看是否是大于或小于你正在寻找的值，它决定了值是否是列表中的第一个或第二个一半。通过子列表跳转到半路上，又比较等，这是pretty的多少人类如何通常查找单词在词典中（虽然我们用更好的启发，很明显 - 如果你要寻找的猫你别在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.

举个例子，假设你是在字母的AZ列表寻找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).

一个线性搜索会问：

列表[0] =='U'？第
     列表[1] =='U'？第
     列表[2] =='U'？第
     列表[3] =='U'？第
     列表[4] =='U'？第
     列表[5] =='U'？第
     ...      列表[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.

二分查找会问：

比较列表[12] （'M'）与'U'：更小，更上看看。 （范围= 13-25）
     比较列表[19] （T），与U：更小，外观更上。 （范围= 20-25）
     比较列表[22] （W），与U：更大，前面看。 （范围= 20-21）
     比较列表[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屋！