数组的查找方法：线性查找二分查找

2020-04-18 刘涛 PV:

前言

从数组中查找你需要的数据，是一个非常常见的需求，那么如何快速的查找你所需要的目标数据呢？这篇文章将为你详细的讲解线性查找与二分法查找，并用 javascript 将其实现希望对各位有所帮助

线性查找

线性查找是一种在数组中查找数据的算法，从数据的头部开始按顺序往下查找即为线性查找

图解实例

如图所示，我们查找的数字 6 在数组中的位置

从数组的最左边开始查找，将其与 6 进行比较，如果结果一致，查找便结束，不一致则向右检查下一个数字。

此处不一致，所以向右继续和下一个数字进行比较。

重复上述操作直到找到数字 6 为止

找到 6 了，查找结束

总结

线性查找需要从头开始不断地按顺序检查数据，因此在数据量大且目标数据靠后，或者目标数据不存在时，比较的次数就会更多，也更为好使。若数据量为 n，线性查找的时间复杂便为 O(n)。

用 js 实现线性查找

我们想要查找某个值在数组中的位置，需要遍历这个数组，判断当前遍历到的值是否与目标值相等。

声明一个函数，参数为：需要查找的数组，需要查找的数据
遍历数组
比较需要查找的数据是否与当前遍历到的数据相等
如果相等则返回当前元素的位置，结束循环
编写代码

const linearSearch = function(arr, target) {
  // 目标元素位置
  let position = -1;
  for (let i = 0; i < arr.length; i++) {
    // 如果当前遍历到的值与目标值相等则返回目标元素的位置
    if (arr[i] === target) {
      position = i;
      return position;
    }
  }
  return position;
};

测试代码

const dataArr = [3, 9, 8, 2, 1, 4, 6, 5, 7];
const position = linearSearch(dataArr, 6);
if (position !== -1) {
  console.log(`目标元素在数组中的位置:${position}`);
} else {
  console.log('目标元素不在数组中');
}

二分查找

二分查找也叫折半查找、平半劈，二分查找的两个条件，有序和顺序，两者缺一不可，意思就是，一条链，不是一盘散沙，如果两点要求没有达到否则就不能使用二分查找法

二分查找通过比较数组中间的数据与目标数据的大小，可以得知目标数据是在数组的左边还是右边。
所以，比较一次就可以把查找范围缩小一半。重复执行该操作接可以找到目标数据，或者得出目标数据不存在的结论

图解实例

我们查找数字 6 在数组中的位置

首先，我们先找到数组中中间的数字，此处为 5

将 5 和要查找的数字 6 进行比较

所以把不需要的数字移除查找范围

在剩下的数组中找到中间的数字，此处为 7

然后我们再来比较 6 和 7

再一次把不需要的数字移除查找范围

在剩下的数组中找到中间的数字，此处为 6

最后我们成功找到目标数字啦 6=6

用 JS 实现二分查找

二分查找只能查找已经排序好的数据，每一次查找都可以将查找范围减半，查找范围内只剩一个数据时查找结束。

声明一个函数，参数为：要查找的数组，要查找的数据，数组的起点，数组的末尾
找到数组的中间值，将其与目标值进行比较
如果中间值大于目标值，可知目标值在中间值的左侧，则对其左边的数据执行上述操作
如果中间值小于目标值，可知目标值在中间值的右侧，则对其右边的数据执行上述操作
直至中间值等于目标值，则结束上述操作，返回中间值的位置。

编写代码

const binarySearch = function(arr, target, start, end) {
  let targetPosition = -1;
  // 计算中间值
  const median = Math.floor((start + end) / 2);
  // 判断中间值与目标值是否相等
  if (arr[median] === target) {
    targetPosition = median;
    return targetPosition;
  }
  // 未找到
  if (start >= end) {
    return targetPosition;
  }
  // 判断中间值是否大于目标值
  if (arr[median] > target) {
    // 递归中间值左侧的数组
    return binarySearch(arr, target, start, median - 1);
  } else {
    // 递归中间值右侧的数组
    return binarySearch(arr, target, median + 1, end);
  }
};

测试代码

const dataArr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const position = binarySearch(dataArr, 6, 0, dataArr.length - 1);
if (position !== -1) {
  console.log(`目标元素在数组中的位置:${position}`);
} else {
  console.log('目标元素不在数组中');
}

区别

本质区别

线性查找可以从乱序数组中找数据，而线性查找只能从已排序好的数组中查找数据。

性能

二分查找利用已排序好的数组，每一次查找都可以将查找范围减半。如果将数量为 n 的数组，将其长度减半 log2n 次后，其中便只剩一个数据了，因此它的时间复杂度为 O(logn)

线性查找需要从头开始不断地按顺序检查数据，因此在数量大且目标数据靠后，或者目标数据不存在时，比较的次数就会更多，也更为耗时。如果数组的数据量为 n，线性查找的时间复杂度便为 O(n)

使用场景

线性查找，数组中的数据可以是无序的，添加数据时无需顾虑位置，直接将其插入到数组的末尾即可，不需要耗费时间。

二分查找，数组中的数据必须是有序的，添加数据时就需要考虑位置，需要消耗一定的时间。

总结

综合上述，如果你查找数据比较频繁的话二分查找更适合你，否则线性查找更适合你。