阅读 1255

数组查找: 线性查找与二分查找

前言

从数组中查找你需要的数据,是一个很常见的需求,那么当你查找所需数据时,用什么方法查找速度最快?

本文将通过图文形式,详细讲解线性查找二分查找,并用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)

从时间复杂度上分析,二分查找相比线性查找速度得到了指数倍的提升。

使用场景

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

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

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

写在最后

  • 文中使用的图片源自《我的第一本算法书》,如若侵权,请评论区留言,作者立即删除相关图片。
  • 文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注😊
  • 本文首发于掘金,未经许可禁止转载💌