51

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

4

11 回答 11

126

线性搜索查找列表，一次一个项目，不跳转。在复杂性方面，这是一次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)
  • 二分查找需要随机访问数据；线性搜索只需要顺序访问（这可能非常重要 - 这意味着线性搜索可以流式传输任意大小的数据）
于 2009-03-31T06:25:17.543 回答
71

可以将其视为在电话簿中查找方式的两种不同方式。线性搜索从头开始，读取每个名称，直到找到所需内容。另一方面，二分搜索是当您打开书本（通常在中间），查看页面顶部的名称，然后确定您要查找的名称是大于还是小于您所要查找的名称'正在寻找。如果您要查找的名称更大，那么您将继续以这种方式搜索书的上半部分。

于 2009-03-31T06:25:24.983 回答
16

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

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

于 2010-09-18T06:50:31.790 回答
5

一定要考虑一下更快的二进制搜索的胜利是否值得保持列表排序的成本（以便能够使用二进制搜索）。即，如果您有很多插入/删除操作并且只是偶尔进行搜索，则二进制搜索总体上可能比线性搜索慢。

于 2009-05-04T20:50:31.580 回答
5

线性搜索从值列表的开头开始，并按顺序逐一检查您要查找的结果。

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

于 2009-03-31T06:26:24.513 回答
3

试试这个：选择一个随机名称“姓氏，名字”并在您的电话簿中查找。

第一次：从书的开头开始，读名字直到找到它，或者找到它按字母顺序出现的地方，并注意它不在那里。

第二次：在中途点打开书，看页面。问问自己，这个人应该在左边还是右边。无论是哪一个，取那个 1/2 并找到它的中间。重复此过程，直到找到条目所在的页面，然后将相同的过程应用于列，或者像以前一样沿页面上的名称线性搜索。

对两种方法都计时并报告！

[还要考虑如果你只有一个名字列表，而不是排序，哪种方法更好......]

于 2009-05-04T20:55:58.837 回答
2

线性搜索查找列表，一次一个项目，不跳转。在复杂性方面，这是一个 O(n) 搜索 - 搜索列表所花费的时间以与列表相同的速度变大。

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

于 2009-06-05T07:49:17.633 回答
2

二进制搜索在 O(logn) 时间内运行，而线性搜索在 O(n) 时间运行，因此二进制搜索具有更好的性能

于 2009-04-28T06:49:16.427 回答
2

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

对于较大的数组，二分查找是有效的。在此我们检查中间元素。如果值大于我们要查找的值，则查看前半部分；否则，查看后半部分。重复此操作，直到找到所需的项目。必须对表进行排序以进行二分查找。它在每次迭代中消除了一半的数据。它是对数的。

如果我们有 1000 个元素要搜索，二分搜索大约需要 10 步，线性搜索需要 1000 步。

于 2009-03-31T06:43:58.170 回答
0

Linear Search查看项目，直到找到搜索到的值。

效率：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 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)

您还可以在此处查看有关线性和二进制搜索的可视化信息：https ://www.cs.usfca.edu/~galles/visualization/Search.html

于 2017-05-25T12:21:23.540 回答
0

为了清楚地理解，请看一下我的 codepen 实现https://codepen.io/serdarsenay/pen/XELWqN

最大的区别是在应用二分搜索之前需要对样本进行排序，因此对于大多数“正常大小”（有争议的）样本，使用线性搜索算法进行搜索会更快。

这是 javascript 代码，对于 html 和 css 以及完整的运行示例，请参阅上面的 codepen 链接。

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;
    }
  }
}
于 2018-04-15T18:20:55.967 回答