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

Question

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

Answer 1

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

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

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

对两种方法计时并报告！

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

Answer 2

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

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

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

Answer 3

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

Answer 4

线性搜索沿着列表向下查找，一次一项，不跳转。 从复杂性的角度来看，这是一个 O(n) 搜索 - 搜索列表所花费的时间以与列表相同的速度变大。

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

Answer 5

线性搜索 查找项目，直到找到搜索到的值。

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

二分查找 查找数组的中间元素。 检查中间值是否大于或小于搜索值。 如果它较小，它将获取数组的左侧并找到该部分的中间元素。 如果更大，则获取数组的正确部分。 它循环操作直到找到搜索到的值。 或者如果数组中没有值则结束搜索。

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

Answer 6

为了清楚地理解，请查看我的 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;
    }
  }
}

Answer 7

线性搜索会向下查找列表，一次一项，不跳转。 从复杂性的角度来看，这是一个 O(n) 搜索 - 搜索列表所需的时间以与列表相同的速度变大。

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

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

线性搜索会问：

列表[0] == 'U'？ 编号
列表[1] == 'U'？ 编号
列表[2] == 'U'？ 编号
列表[3] == 'U'？ 编号
列表[4] == 'U'？ 编号
列表[5] == 'U'？ 编号
...
列表[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)。
• 二分搜索需要随机访问数据； 线性搜索只需要顺序访问（这可能非常重要 - 这意味着线性搜索可以流任意大小的数据）

Answer 8

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

Answer 9

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

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

Answer 10

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

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

Answer 11

确保仔细考虑更快的二分搜索的胜利是否值得付出保持列表排序的成本（以便能够使用二分搜索）。 即，如果您有大量插入/删除操作并且只有偶尔的搜索，则二分搜索总体上可能比线性搜索慢。