线性search和二进制search有什么区别？
线性search和二进制search有什么区别？
线性search按顺序查看一个列表，一次一个，不跳跃。 在复杂性方面，这是一个O(n)search – search列表花费的时间以与列表相同的速率变大。
二分search是指从sorting列表的中间开始，查看它是大于还是小于要查找的值，这决定了该值是在列表的前半部分还是后半部分。 跳到子列表的一半，然后再比较一下。这几乎是人类通常在字典中查找单词的方法（尽pipe我们使用了更好的启发式方法，显然 – 如果你正在寻找“猫”，你不需要从“M”开始）。 在复杂性方面，这是一个O(log n)search – search操作的数量比列表的增长速度要慢，因为每次操作都会减半search空间。
举个例子，假设你在AZ列表中查找U（索引0-25;我们正在索引20的值）。
线性search会问：
list[0] == 'U'？ 没有。
list[1] == 'U'？ 没有。
list[2] == 'U'？ 没有。
list[3] == 'U'？ 没有。
list[4] == 'U'？ 没有。
list[5] == 'U'？ 没有。
…list[20] == 'U'？ 是。 成品。
二进制search会问：
比较
list[12]（'M'）和'U'：小一点，再看看。 （范围= 13-25）
比较list[19]（'T'）和'U'：小一点，继续往下看。 （范围= 20-25）
比较list[22]（'W'）和'U'：更大，更早看。 （范围= 20-21）
比较list[20]（'U'）和'U'：find它！ 成品。
比较两者：
- 二进制search要求对input数据进行sorting; 线性search没有
- 二进制search需要进行sorting比较; 线性search只需要进行相等比较
- 二进制search具有复杂度O（log n）; 如前所述，线性search具有复杂性O（n）
- 二进制search需要随机访问数据; 线性search只需要顺序访问（这可能非常重要 – 这意味着一个线性search可以传输任意大小的数据）
把它看作是在电话簿中find你的方式的两种不同的方式。 线性search从一开始就开始，读取每一个名字，直到find你要找的东西。 另一方面，二进制search是当你打开书本（通常在中间），看看页面顶部的名字，然后决定你要找的名字是大于还是小于你的名字正在寻找。 如果你要找的名字比较大，那么你继续以这种方式search这本书的上半部分。
我想补充一个差异 –
对于线性search值，不需要sorting。
但是对于二进制search，值必须按sorting顺序。
线性search通过查看数据列表中的每个元素来工作，直到find目标或到达结尾。 这导致给定列表上的O（n）性能。 二进制search带有必须对数据进行sorting的先决条件。 我们可以利用这些信息来减less我们需要查看的项目数量，以find我们的目标。 我们知道，如果我们查看数据中的随机项（比如说中间项），并且该项大于我们的目标，则该项右侧的所有项也将大于我们的目标。 这意味着我们只需要查看数据的左边部分。 基本上，每次我们search目标和错过，我们可以消除剩余的一半项目。 这给了我们一个很好的O（log n）时间复杂度。
请记住，即使使用最有效的algorithm，sorting数据总是比线性search更慢（最快的sortingalgorithm是O（n * log n））。 所以你不应该为了稍后执行一个二进制search而sorting数据。 但是，如果您要进行多次search（至less要进行O（log n）次search），则可能需要对数据进行sorting，以便执行二进制search。 在这种情况下，你也可以考虑其他数据结构，例如哈希表。
线性search从值列表的开始处开始，然后逐个检查，以便查找结果。
二进制search从sorting的数组中间开始，并确定您正在查找的值（如果有的话）的哪一侧。 然后以相同的方式再次search该arrays的“一半”，每次将结果除以二。
请务必仔细考虑更快二进制search的胜利是否值得保持列表sorting的成本（为了能够使用二进制search）。 也就是说，如果你有很多的插入/删除操作，只有偶尔的search二进制search总的来说可能比线性search慢。
试试这个：select一个随机的名字“姓氏，名字”，并在你的电话簿中查找。
第一次：从书的开头开始，读取名字，直到find它，或者find它将按字母顺序发生的地方，注意它不在那里。
第二次：在中途点打开书看看页面。 问问你自己，这个人应该是左边还是右边。 无论是哪一个，拿起这个1/2，find它的中间。 重复此过程，直到find条目所在的页面，然后对列应用相同的过程，或者像以前一样沿着页面上的名称进行线性search。
时间两种方法，并报告回来！
[也考虑如果你所拥有的是一个名称列表，还没有sorting…]
也称为顺序search的线性search从头开始依次查看每个元素，以查看数据结构中是否存在期望的元素。 当数据量很小时，这个search是快速的。它很容易但是所需要的工作量与要search的数据量成比例。如果所期望的元素不存在，则元素数目将增加一倍。
二进制search对较大的数组是有效的。 在这里我们检查中间元素。如果值大于我们要查找的值，那么看上半部分;否则，看下半部分。 重复此操作，直到find所需的项目。 该表必须进行二进制searchsorting。 它在每次迭代中消除了一半的数据。它是对数的。
如果我们有1000个元素进行search，二进制search需要大约10个步骤，线性search1000个步骤。
二进制search运行在O（logn）时间，而线性search运行在O（n）次，因此二进制search具有更好的性能
线性search按顺序查看一个列表，一次一个，不跳跃。 在复杂性方面，这是一个O（n）search – search列表花费的时间以与列表相同的速率变大。
二分search是指从sorting列表的中间开始，查看它是大于还是小于要查找的值，这决定了该值是在列表的前半部分还是后半部分。 跳到子列表的一半，然后再比较一下。这几乎是人类通常在字典中查找单词的方法（尽pipe我们使用了更好的启发式方法，显然 – 如果你正在寻找“猫”，你不需要从“M”开始）。 在复杂性方面，这是一个O（log n）search – search操作的数量比列表的增长速度要慢，因为每次操作都会减半search空间。
Linear Search将查看项目直到findsearch的值。
效率： O(n)
Python代码示例：
test_list = [1, 3, 9, 11, 15, 19, 29] test_val1 = 25 test_val2 = 15 def linear_search(input_array, search_value): index = 0 while (index < len(input_array)) and (input_array[index] < search_value): index += 1 if index >= len(input_array) or input_array[index] != search_value: return -1 return index print linear_search(test_list, test_val1) print linear_search(test_list, test_val2)
Binary Searchfind数组的中间元素。 检查中间值大于还是小于search值。 如果它较小，它会得到数组的左侧并find该部分的中间元素。 如果更大，则获取数组的右侧部分。 它循环操作，直到findsearch的值。 或者，如果数组中没有值完成search。
效率： O(logn)
Python代码示例：
test_list = [1, 3, 9, 11, 15, 19, 29] test_val1 = 25 test_val2 = 15 def binary_search(input_array, value): low = 0 high = len(input_array) - 1 while low <= high: mid = (low + high) / 2 if input_array[mid] == value: return mid elif input_array[mid] < value: low = mid + 1 else: high = mid - 1 return -1 print binary_search(test_list, test_val1) print binary_search(test_list, test_val2)
你也可以在这里看到有关线性和二进制search的可视化信息： https ： //www.cs.usfca.edu/~galles/visualization/Search.html
