如何从数据组里查找一个元素所在的位置

如何从数据组里查找一个元素所在的位置

有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

回到顶部