查找最接近给定索引的javascript稀疏数组索引

Question

假设我有一个稀疏数组，其值为“foo”，赋值为索引100，值“bar”赋值给索引130.我怎样才能“舍入”任何给定的索引这样它总是返回最近定义的索引的值？

例如：如果我试图获得索引103的值，我应该得到“富”而不是未定义的。同样，99的过低指数仍然应该给我“foo”，而115应该在指数130四舍五入到“bar”。

这应该完全独立于（和无关）存储在指数。

编辑：使用密集阵列和一个包围搜索在 O（日志（n））的时间解决 O（n）的时间。请注意，这要求将浓缩阵列从低到高排序。

var sparseArr = []; 
sparseArr[100] = "foo"; 
sparseArr[130] = "bar"; 
sparseArr[150] = "foobar"; 

var condensedArr = [100, 130, 150]; 

function roundGet(index) { 
    var mid; 
    var lo = 0; 
    var hi = condensedArr.length - 1; 
    while (hi - lo > 1) { 
    mid = Math.floor((lo + hi)/2); 
    if (condensedArr[mid] < index) { 
     lo = mid; 
    } else { 
     hi = mid; 
    } 
    } 
    if (index - condensedArr[lo] <= condensedArr[hi] - index) { 
    return sparseArr[condensedArr[lo]]; 
    } 
    return sparseArr[condensedArr[hi]]; 
} 

例在https://jsfiddle.net/xfevha56/

Answer 1

你可以使用Array#some，其迭代只有非项目疏林。

function roundGet(index) { 
 
    var last = -Infinity, 
 
     value; 
 
    a.some(function (v, i) { 
 
     if (Math.abs(last - index) <= Math.abs(i - index)) { 
 
      return true; 
 
     } 
 
     value = v; 
 
     last = i; 
 
    }); 
 
    return value; 
 
} 
 

 
var a = []; 
 
a[100] = 'foo'; 
 
a[130] = 'bar'; 
 
a[150] = 'foobar'; 
 

 
console.log(roundGet(0)); // "foo" 
 
console.log(roundGet(99)); // "foo" 
 
console.log(roundGet(103)); // "foo" 
 
console.log(roundGet(115)); // "foo" 
 
console.log(roundGet(116)); // "bar" 
 
console.log(roundGet(186)); // "foobar" 
 
console.log(roundGet(1000)); // "foobar"

ES6

function roundGet(index) { 
 
    var last = -Infinity, 
 
     value; 
 
    a.some((v, i) => 
 
     Math.abs(last - index) <= Math.abs(i - index) || (value = v, last = i, false)); 
 
    return value; 
 
} 
 

 
var a = []; 
 
a[100] = 'foo'; 
 
a[130] = 'bar'; 
 
a[150] = 'foobar'; 
 

 
console.log(roundGet(0)); // "foo" 
 
console.log(roundGet(99)); // "foo" 
 
console.log(roundGet(103)); // "foo" 
 
console.log(roundGet(115)); // "foo" 
 
console.log(roundGet(116)); // "bar" 
 
console.log(roundGet(186)); // "foobar" 
 
console.log(roundGet(1000)); // "foobar"

Answer 2

你还没谈到浏览器支持什么，所以这里是使用一些数组操作功能（IE9 +）和ES2015功能箭头语法的解决方案。

function findIndex(array, searchedIndex) { 
    return Object.keys(array) 
       .map(e => ({val: parseInt(e, 10), abs: Math.abs(parseInt(e, 10) - searchedIndex)})) 
       .reduce((min, e) => min[0].val > e.abs ? [{val: e.abs, i: e.val}] : min, [{val: Number.MAX_VALUE, i: -1}]) 
       .reduce((v, min) => min.val !== Number.MAX_VALUE ? array[min.i] : v, -1) 
} 

你可以试试Babel online REPL。

Answer 3

您可能会这样做;

function findCloseIndex(a,idx){ 
 
    return Object.keys(a) 
 
       .map(k => [k,Math.abs(k-idx)]) 
 
       .sort((a,b) => a[1] - b[1])[0][0]; 
 
} 
 

 
var arr = [], 
 
    close; 
 

 
arr[100] = "foo"; 
 
arr[130] = "bar"; 
 

 
close = arr[findCloseIndex(arr,125)]; 
 
console.log(close); 
 
close = arr[findCloseIndex(arr,78)]; 
 
console.log(close);