前言
从数组中查找你需要的数据，是一个很常见的需求，那么当你查找所需数据时，用什么方法查找速度最快？
本文将通过图文形式，详细讲解线性查找与二分查找，并用JavaScript将其实现，欢迎各位感兴趣的前端开发者阅读本文。
线性查找
概念
线性查找是一种在数组中查找数据的算法，从数组的头部开始按顺序往下查找即为线性查找。
图解示例
如图所示，我们查找数字6在数组中的位置
- 从数组的最左边开始查找，将其与6进行比较，如果结果一致，查找便结束，不一致则向右检查下一个数字。
- 此处不一致，所以向右继续和下一个数字进行比较。
- 重复上述操作直到找到数字6为止
- 找到6了，查找结束
线性查找需要从头开始不断地按顺序检查数据，因此在数据量大且目标数据靠后，或者目标数据不存在时，比较的次数就会更多，也更为好使。若数据量为n，线性查找的时间复杂便为O(n)。
用JS实现线性查找
正如图解示例所述，我们想要查找某个值在数组中的位置，需要遍历这个数组，判断当前遍历到的值是否与目标值相等。
- 声明一个函数，参数为：需要查找的数组，需要查找的数据
- 遍历数组
- 比较需要查找的数据是否与当前遍历到的数据相等
- 如果相等则返回当前元素的位置，结束循环
接下来，我们将上述实现思路转化为代码
- 编写线性查找函数
/**
* 线性查找函数
* @param arr 需要进行查找的数组
* @param target 需要查找的数据
* @returns {number} 返回值
*/
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实现二分查找
正如图解示例所述，二分查找只能查找已经排序好的数据，每一次查找都可以将查找范围减半，查找范围内只剩一个数据时查找结束。
- 声明一个函数，参数为：要查找的数组，要查找的数据，数组的起点，数组的末尾
- 找到数组的中间值，将其与目标值进行比较
- 如果中间值大于目标值，可知目标值在中间值的左侧，则对其左边的数据执行上述操作
- 如果中间值小于目标值，可知目标值在中间值的右侧，则对其右边的数据执行上述操作
- 直至中间值等于目标值，则结束上述操作，返回中间值的位置。
我们将上述思路转化为代码
- 编写二分查找函数
/**
* 二分查找
* @param arr 查找的数组
* @param target 查找的数据
* @param start 数组的开始位置
* @param end 数组的末尾位置
* @returns {number}
*/
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)
从时间复杂度上分析，二分查找相比线性查找速度得到了指数倍的提升。
使用场景
线性查找，数组中的数据可以是无序的，添加数据时无需顾虑位置，直接将其插入到数组的末尾即可，不需要耗费时间。
二分查找，数组中的数据必须是有序的，添加数据时就需要考虑位置，需要消耗一定的时间。
综合上述，如果你查找数据比较频繁的话二分查找更适合你，否则线性查找更适合你。
写在最后
- 文中使用的图片源自《我的第一本算法书》，如若侵权，请评论区留言，作者立即删除相关图片。
- 文中如有错误，欢迎在评论区指正，如果这篇文章帮到了你，欢迎点赞和关注😊
- 本文首发于掘金，未经许可禁止转载💌
评论区