如何从数据组里查找一个元素所在的位置
如何从数据组里查找一个元素所在的位置
有2种应用场景:
一:把一个新元素插入到指定数组 (数组元素按序排列)
二:找出数组是否包含某个元素,找到他的位置
第一种情况必须要求元素是按序排列的,否则我们无法给预定元素找到它的位置.
var a=[1000,2000,2018,2909,3000,4000,4210,4390,5000]; var b=4500;
思路:
假设数组元素升序排列
我们只需要找到第一个大于插入值的元素即可,目标元素就在此元素前一个位置.
方法:
遍历元素,找到第一个大于或者等于插入值的元素位置.
下面实现了一个通用的遍历数组元素比较方法
function commonFind(arr,aim){
var left=-1,right=-1;
for(var i=0;i<arr.length;i++){
if(aim>arr[i])
left=i;
if(aim<arr[i])
right=i;
if(aim==arr[i])
left=right=i;
if(right>-1)
return Math.round((left+right)/2);
}
}
console.log(commonFind(a,b))如图我们看到 4500 在a数组的第九位 (索引从0开始)
还有一种思路:
我们想到了折半查找法,就是对于一个已经排序过的数组来说,我可以用要插入的元素去和数组中间元素比较,然后来确定元素应该插入数组前半段还是后半段,假设我们确定插入了后半段,接着我们可以继续用元素和后半段的中间元素来比较,依次类推,最后知道我们不能分割时就找到了插入元素的位置了.
看来我们要实现一个递归方法了.
function halfMethod(arr,aim,start,end,lastStart,lastEnd){
if(start>end)
return -1;
if(lastStart>-1&&lastEnd>-1)
return Math.round((lastStart+lastEnd)/2);
else{
var mid=Math.round((start+end)/2);
if(aim==arr[mid])
return halfMethod(arr,aim,mid,mid,mid,mid);
else if(aim<arr[mid])
return halfMethod(arr,aim,start,mid,lastStart,mid);
else if(aim>arr[mid])
return halfMethod(arr,aim,mid,end,mid,lastEnd);
}
}看上去很繁琐,其实很简单.
参数说明:
arr 是查找的数组
aim 是准备插入的元素
start 数组查找起始范围
end 数组查找结束范围
lastStart 是记录最后一次小于目标元素的索引值
lastEnd 最后一次大于目标元素的索引值
为什么这样?
仔细想想,当我们找到最后一次小于目标元素的值,和最后一次大于目标元素的值时,这次数组已经分割到了最小,已经不能继续分割.这正是我们要插入的位置.返回我们要的索引值,结束递归调用
console.log('目标位置', halfMethod(a,b,0,a.length,-1,-1));上面说到的2种方法都是将新元素插入到指定数组中,现实中我们还遇到好多在数组中查找某个元素的位置,下面我们一并介绍一下.
在数组中查找某个元素的位置
我们同样是用上面的2中方法来实现.
第一种,遍历数组,比较每个元素,找到和目标元素值相当的元素,返回其索引.
function commonFindElement(arr,aim){
var rtn=-1;
for(var i=0;i<arr.length;i++)
if(aim==arr[i])
rtn=i;
return rtn;
}var c=2909;
console.log('目标元素',commonFindElement(a,c));a数组我们依然是最上面定义的数组不变,c 变量2909 是数组中的一个元素,我们看下能否准备返回所在索引位置
第二种方法使用折半查找法来实现
function splitFind(arr,aim,start,end){
if(start>end)
return -1;
var mid=Math.round((start+end)/2);
if(arr[mid]==aim)
return mid;
else if(arr[mid]>aim)
return splitFind(arr,aim,start,mid);
else if(arr[mid]<aim)
return splitFind(arr,aim,mid,end);
else
return -1;
}console.log('目标元素',splitFind(a,c,0,a.length));上面的递归方法只有4个参数,和插入元素相比逻辑简单了很多.如果找不到返回 -1
系能测试:
1.用一个循环填充5000个元素的 a 数组
for(var i=0;i<5000;i++){
a.push(i);
}然后查找 4500 元素该插入的位置 和 元素 2900 在数组中的位置.
可见折半查找法并没有发挥出性能,计算插入的索引使用2毫秒 ,普通循环方法使用 0毫秒.
计算元素在数组中的位置时,折半查找和普通查找相同,都是 2毫秒.
2.将 a 数组填充 50000 个元素, 查找 45000 该插入的位置 和 元素 29000 在数组中的位置.
当数量级上万时,明显看到折半查找法的优势出来了.
3.将 a 数组填充 5000000 个元素,查找 4500000 该插入的位置 和 元素 2900000 在数组中的位置.
折半查找元素插入数组的性能 高出普通方法 7倍.
折半查找元素所在位置的性能 高出普通方法N倍.
代码地址: https://github.com/zzhi191/demo/blob/master/findInArray.js