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

Question

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

- Smi

---

请阅读您的课程材料中相应的部分，这些部分理应由您的教师精心挑选和准备。如果没有，可以通过维基百科、C2或谷歌搜索来回答这类问题。此外，在网上也可以找到很多精心制作的课程/讲座笔记。 - user166390

Answer 1

一个线性搜索逐个查看列表中的项目，不跳过任何一个。从复杂度上来说，这是一种O(n)搜索——搜索列表所需的时间随着列表的增长而增加。

二分搜索是指从已排序的列表中间开始，看它是否大于或小于您要查找的值，从而确定该值在列表的第一半还是第二半中。然后跳到子列表的中间位置，再次进行比较等等。这基本上就是人类在字典中查找单词的方式（当然我们使用更好的启发式方法——如果你要查找“猫”，你不会从“M”开始）。从复杂度上来说，这是一种O(log n)搜索——搜索操作的数量增长速度比列表慢，因为每次操作都将“搜索空间”减半。

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

线性搜索会问：

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)，如前所述
• 二分查找需要随机访问数据；线性查找只需要顺序访问（这非常重要——这意味着线性查找可以流式传输任意大小的数据）

- Jon Skeet

---

+1，虽然我不是特别喜欢你的字典比喻。一个更好的比喻是“猜我心中的数字（1到100之间）”游戏，回答可以是“你猜对了”、“太高了”或者“太低了”。 - Adam Rosenfield

我认为使用字典类比是可以的，尽管它更适合插值搜索。 - Nick Johnson

字典类比对我来说更好...如果我们考虑到数据库中的低、等于或大于加索引。 - A.T.

采用字典方法，最重要的是排序。因此，在开始二分查找之前，必须确保数据已经排序。如果没有排序，你将会在整个数据范围内跳来跳去，却找不到目标值 : )。如果你不标记已经尝试过的值，情况可能会更糟。所以一定要进行排序。这里可以找到一些基于Java的二分查找实现：http://www.digizol.com/2013/08/java-binary-search-recursive-testcases.html。 - lkamal

@lkamal：是的，输入数据已排序的要求是我的第一个要点... - Jon Skeet

@JonSkeet 没错 - 我只是想强调字典是正确的，而且在我看来也是正确的。 - lkamal

Answer 2

你可以将这个过程想象成在电话簿中寻找联系人的两种不同方式。线性查找是从开始处开始，逐个读取每个姓名，直到找到目标为止。而二分查找则是打开电话簿(通常在中间)，查看页面顶部的姓名，并判断你要查找的姓名是比这个姓名大还是小。如果你要查找的姓名较大，则继续按照这种方式搜索电话簿的上半部分。

- Banang

---

非常好的比喻，用非常少的文字解释清楚了！恭喜！ - Peter Parker

迄今为止，2016年看来这是最有效的答案！ - Kebab Programmer

非常值得铭记的例子。非常感谢。 - Sumith Harshan

讲解得非常好，简单易懂，给人留下深刻印象，真棒！ - Mr. Patel

Answer 3

线性搜索通过查看数据列表中的每个元素，直到找到目标或到达末尾。这会导致在给定列表上的O(n)性能。

二分搜索的前提是数据必须排序。我们可以利用这些信息来减少查找目标所需查看的项数。如果我们查看数据中的随机项（假设是中间项），并且该项大于我们的目标，则右侧所有项也将大于我们的目标。这意味着我们只需要查看数据的左侧部分。基本上，每次搜索目标并未命中时，我们就可以排除剩余项的一半。这为我们提供了一个很好的O(log n)时间复杂度。

请记住，即使使用最有效的算法对数据进行排序，速度也始终比线性搜索慢（最快的排序算法是O(n*log n)）。因此，您不应仅仅为了执行单个二分搜索稍后再对数据进行排序。但是，如果您将执行多个搜索（至少O(log n)次搜索），则有必要对数据进行排序，以便进行二分搜索。在这种情况下，您还可以考虑其他数据结构，例如哈希表。

- antar

Answer 4

线性搜索从值列表的开头开始，按顺序逐个检查所寻找的结果。

二分搜索从排序数组的中间开始，并确定您要查找的值在哪一侧（如果有）。然后，以相同的方式再次搜索该“半”数组，每次将结果减半两次。

- jthompson

Answer 5

请务必仔细考虑，是否值得为了使用二分查找而保持列表排序（即使这样做的代价很高）。例如，如果您需要频繁进行插入/删除操作，但只偶尔进行搜索，则总体而言，二分查找可能比线性查找更慢。

- knweiss

Answer 6

尝试一下：随机选择一个名字“Lastname，Firstname”，并在电话簿中查找。

第一次：从书的开头开始阅读名称，直到找到它为止，否则找到按字母顺序出现的位置，并注意到它不在那里。

第二次：将书打开到中间位置并查看页面。问自己，这个人应该在左边还是右边。无论哪个方向，都要取1/2并找到其中间点。重复此过程，直到找到应该输入的页面，然后对列应用相同的过程，或者像之前一样在线性地沿着页面上的名称进行搜索。

计时两种方法并报告结果！

[还要考虑如果您只有一个未排序的名称列表，哪种方法更好...]

- simon

Answer 7

线性搜索按顺序逐项查看列表，没有跳跃。在复杂度方面，这是一种O(n)搜索 - 搜索列表所需的时间与列表大小以相同的速率增长。

二分搜索是从排序列表的中间开始，查看该值是否大于或小于要查找的值，以确定该值是否位于列表的第一半或第二半中。跳转到子列表中间位置，再次进行比较等等。这基本上就是人们在字典中查找单词的方式（尽管我们显然使用更好的启发式方法 - 如果你正在查找“cat”，你不会从“M”开始）。在复杂度方面，这是一种O(log n)搜索 - 搜索操作的数量增长比列表更慢，因为每个操作都将“搜索空间”减半。

- Vijay

Answer 8

线性搜索，也称为顺序搜索，按照顺序从开始的每个元素开始查看数据结构中是否存在所需的元素。当数据量很小时，这种搜索会很快。它很容易但需要搜索的数据量与工作量成正比。如果所需的元素不存在，则元素数量加倍将使搜索时间加倍。

二分搜索对于较大的数组效率更高。我们检查中间元素。如果该值大于我们正在查找的值，则在第一半中查找；否则，在第二半中查找。重复此过程直到找到所需的项。二分搜索需要对表进行排序。它每次迭代都会减少一半的数据，因此具有对数级别的复杂度。

如果要搜索1000个元素，则二分搜索需要约10步，线性搜索需要1000步。

- Prabhu. S

---

@Prabu - 不正确 - 最好的情况是1，最坏的情况是1000，平均值为500。 - mP.

Answer 9

二分查找的时间复杂度是O(logn)，而线性查找的时间复杂度是O(n)，因此二分查找具有更好的性能。

- Vijay

Answer 10

为了更好的理解，请查看我的codepen实现 https://codepen.io/serdarsenay/pen/XELWqN 最大的区别是需要在应用二分搜索之前对样本进行排序，因此对于大多数“正常大小”的（这里指可以争论的）样本，使用线性搜索算法将更快。

以下是JavaScript代码，请参考上述codepen链接获取HTML和CSS以及完整运行示例。

var unsortedhaystack = [];
var haystack = [];
function init() {
  unsortedhaystack = document.getElementById("haystack").value.split(' ');
}
function sortHaystack() {
  var t = timer('sort benchmark');
  haystack = unsortedhaystack.sort();
  t.stop();
}

var timer = function(name) {
    var start = new Date();
    return {
        stop: function() {
            var end  = new Date();
            var time = end.getTime() - start.getTime();
            console.log('Timer:', name, 'finished in', time, 'ms');
        }
    }
};

function lineerSearch() {
  init();
  var t = timer('lineerSearch benchmark');
  var input = this.event.target.value;
  for(var i = 0;i<unsortedhaystack.length - 1;i++) {
    if (unsortedhaystack[i] === input) {
      document.getElementById('result').innerHTML = 'result is... "' + unsortedhaystack[i] + '", on index: ' + i + ' of the unsorted array. Found' + ' within ' + i + ' iterations';
      console.log(document.getElementById('result').innerHTML);
      t.stop(); 
      return unsortedhaystack[i]; 
    }
  }
}

function binarySearch () {
  init();
  sortHaystack();
  var t = timer('binarySearch benchmark');
  var firstIndex = 0;
  var lastIndex = haystack.length-1;
  var input = this.event.target.value;

  //currently point in the half of the array
  var currentIndex = (haystack.length-1)/2 | 0;
  var iterations = 0;

  while (firstIndex <= lastIndex) {
    currentIndex = (firstIndex + lastIndex)/2 | 0;
    iterations++;
    if (haystack[currentIndex]  < input) {
      firstIndex = currentIndex + 1;
      //console.log(currentIndex + " added, fI:"+firstIndex+", lI: "+lastIndex);
    } else if (haystack[currentIndex] > input) {
      lastIndex = currentIndex - 1;
      //console.log(currentIndex + " substracted, fI:"+firstIndex+", lI: "+lastIndex);
    } else {
      document.getElementById('result').innerHTML = 'result is... "' + haystack[currentIndex] + '", on index: ' + currentIndex + ' of the sorted array. Found' + ' within ' + iterations + ' iterations';
      console.log(document.getElementById('result').innerHTML);
      t.stop(); 
      return true;
    }
  }
}

- sed