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


前语

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

本文将经过图文形式,详细解说线性查找二分查找,并用JavaScript将其完成,欢迎各n a . 7 y q B位感兴趣的前端开发V ; 6 @ i q K k者阅览本文。

线性查找

概念O u t q u & 5

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

图解示例

如图所示,咱们查找数字6在数组中的方位

数组查找: 线性查找与二分查找
  • 从数组的最左面开始查找,将其与6进行比较,假如结果一致,查找便完毕,不一致则向右查看下一个数字。
数组查找: 线性查找与二分查找
  • 此处不一致,所以向右继d ! r V y b t q i续和下一个数字进行T f K * ( , 9 w o比较。
数组查找: 线性查找与二分查找
  • 重复上述操作直到找到数字6为止
数组查找: 线性查找与二分查找
  • 找到6了,查找完毕
数组查找: 线性查找与二分查找

线性查找需求从头开始不断地按& ( o次序查看数据,因而在数据i * P ^ T e h 5量大且方针数据靠后,或许方针数据不存在时,比较的次数就会更多,也更为好使。若数据量为n,线性查找^ * I – l e t c的时刻杂乱便为O(n)。

用JS完成线性查找

正如图解示例所述,咱们想要查找某个值在数组c f $ J R 5 o G 2中的方位,需求遍历这个数组,判别当时遍历到的值是否与方针值持平。

  • 声明一个函数,参数为:需求查找的c ) D Z s数组,需求查找的数据
  • 遍历数组
  • 比较需求查找的数据是否与当时U e Q遍历到的数据持平
  • 假如持平则回来当时元素的方位,完毕循环

接下来,咱g * – K =们将上述完成思路转化为代码

  • ` p U写线性查找函数
/**
*% 4 * J { K 线性查找函数
* @param arr 需求进行查找的数组
* @param target 需求查找的数据
* @returns {number} 回来值
*/
const linearSearch = fux k 4 e C , Vnction (arrP # K,target) {
// 方针元素方位
let position = -1;
for (let i = 0; i < arr.lenG # A u - * Y ~ Rgth; i++){
// 假如当时遍历到的值与方针值持平则回来方u { a _ r针元素的方位
if(arr[i] === target){
position = i;
returu | B S . D x / 6n po_ S Z ] |sition;
}
}
return position;
}

接下来0 R C j B t $ [ y,咱们测验下方才编写的线性查找函数

const dataArr = [3T O 9 P V m e,e s # D } ] 2 :9,8,2,1,4,6,5,7H ? w G o H];
const position = linearSearch(dataArr,6);
if(position !== -1){
console.log(`方针元素在数组中的方位:${position}`);
}else{
console.log("方针元素不在数组中");
}
数组查找: 线性查找与二分查找

二分查找

概念

二分查找也是一种在数组中查找数据的算法,它只能查找现已排序好的数据。

二分查找经过比较数T n K 9组中心的数据与方针数据的巨细,能够得知方针数据是在数组的左面仍是右边。

因而,比较一次就能够把查找规模缩小一半。重l J T复履行该操作接能够找到方针数据,或许得出方针数据不存在的结论。

图解示例

如图所示,咱们3 / O查找数字6在数组中的方位

数组查找: 线性查找与二分查找
  • 首要,找到0 ] + @ Q U ]数组中心的数字,此处为5.
数组查找: 线性查找与二分查找
  • 将5和要查找的数字6进行比较
数组查找: 线性查找与二分查找
  • 把不需求的数字移出查找规模
数组查找: 线性查找与二分查找
  • 在剩下的数组中找到中心的数字,此处为7
数组查找: 线性查找与二分查找
  • 比较6和7
数组查找: 线性查找与二分查找
  • 把不需求的数字移出查找规模
数组查找: 线性查找与二分查找
  • 在剩下的数组中找到中心的数字,此处为6
数组查找: 线性查找与二分查找
  • 6=6,成功找到方针数字
数组查找: 线性查找与二分查找

用JS完成二分查找

正如图解示例所述,二分查找只能查找现已排序好的数据,每一次查找都能够将查找规模折半,查找规模内只剩一个数据时查找完毕。

  • 声明一个函数,参数为:要查找的数组,要查找的数据,数组的起点,数组的结尾
  • } I 5 { 1 z R o到数组O ! d的中心值,将其与方针值进行比较
  • 假如中心值大于方针值,可知方针值在m y L ?中心值的左边,则对其左面的数据履行上述操作
  • 假如中心值小于方针值,可知方针值在中心值的右侧,则对其右边的数据履行上述操作
  • 直至中心值等于方针值,则完毕上述操作,回来中心值的方位。

咱们将上述思路转化为代码

  • 编写二分查找函数
/**
* 二分查找
* @param arr 查找的数组
* @param target 查找的数据
* @param start 数组的开始方位
* @param end 数组的结尾方位
* @returns {numbeO / , ~ m fr}
*/
const binarySearch = function (arr,target,start,end) {
let targetPosition = -1;
// 计算中心值
const median =) { 6 1 Q Math.floor([ x 0 } 0 z ` U k(start + end) / 2);
// 判别中心值与方针值是否持平
if(arr[mQ M # / G T & , Sedian] === target){
targetPosih d ^ y E Ftion = median;| m & q I % x G
return targetPo] & g t & , g 7sition;
}
// 未找到
if(starto ! , u / L O >= end){
return targetPosition;_ 1  Y
}
// 判别中心值是否大于方针值
if(arr[median] > target){
// 递归中心值左边的数组
r6 K ueturn binaryS5 & h $ ^ { { earch(arr,target,start,median - 1)
}else{
// 递归中心j z c s =值右侧的数组
return binarySearch(arr,target, median + 1, end);
}
};

接下来,咱们来测验下方才编写的二分查找函数

const dataArr = [1,2,3,4,5,6,7,8,9];
const position = binarySearch(dataArr,6,0,dat ] : h I ( mtaArr.length - 1);
if(position !== -1){
console.log(`方针元素在数组中的方位:${position}`)
}else{
console.log(. Q ^ ?"方针元素不在数组中");
}
数组查找: 线性查找与二分查找

线性查S . R b j { I l找与二分查找的区别

本质区别

线性查找能够从乱序数组中找数据,而二分查找只能从已排序好的数组中查找数据。

功能

二分查找利用已排序好的= g | S 5 q数组,每一次查找都能够将} 4 I查找规模折半。假如将数量为n的数组,将其长度折半log2n次后,其间便只剩一个数据了,因而它的时刻杂乱度为O(logn)

线性查找需求从头开始不断地按次序查X – N R T ;看数据,因而在数量大且方针数据靠后,或许方针数据不存在时,比较的次数就会更多,也更为耗时。假如数组的数据量为, 7 , x ? Mn,线性查找的时刻杂乱度便为O(n)

从时刻杂乱度上剖析,二分查找比较线性查找速度得到了J ) ^指数倍的提升。

运用场景

线性查找,数组中的数据能够是无序的,增加数据时无需顾虑方位,直接将其插入到数组的结尾即可,不需求耗费时刻。

二分查找,数组中的数据必须是有序的,增加数据时就需求考虑方位,需求耗费一定的时刻。

归纳上述,假如你查找数据比较频繁的话二分查找更适合你,不然线性查找更适合你。

写在最后

  • 文中运用的图片源自《我的第一本算法书》,如若侵权,请评论区留言,& – a _作者当即删去相关图片。
  • 文中如有错误,欢迎在评论B # e区纠正,假如这篇文章帮到了你,欢迎点赞和关注
  • 本文首发于掘金,未经许可禁止转载

发表评论

提供最优质的资源集合

立即查看 了解详情