在 Javascript 中的对象数组中进行高效搜索

Question

假设我有一个预先排序的对象数组，例如这个：

let data = [
    { moment: '00:01', otherProp: 'something', somethingMore: 'someelse'},
    { moment: '01:10', otherProp: 'something', somethingMore: 'someelse'},
    { moment: '05:37', otherProp: 'something', somethingMore: 'someelse'},
    { moment: '07:51', otherProp: 'something', somethingMore: 'someelse'},
    //and so on
]

我输入的 x 被格式化为 hour:minutes 字符串（例如 x='06:05'），我需要找到两个连续的对象（data[i] 和 data [i+1]) 这样 data[i].moment <= x < data[i+1].moment

假设数组有将近 200 个元素，我需要以最快的方式找到结果。我必须从头开始实施二进制搜索吗？有我可以使用的图书馆吗？

Answer 1

Do i've to implement the binary search from scratch?

有什么意义？只是几行代码：

let data = [
    { moment: '00:01', otherProp: 'something', somethingMore: 'someelse'},
    { moment: '01:10', otherProp: 'something', somethingMore: 'someelse'},
    { moment: '05:37', otherProp: 'something', somethingMore: 'someelse'},
    { moment: '07:51', otherProp: 'something', somethingMore: 'someelse'},
    //and so on
];
let search = '06:05';

let lo = -1, hi = data.length-1, mid;
while(hi > lo){
  if(data[mid=(lo+hi+1)>>1].moment > search) {
    hi = mid-1;
  } else {
    lo = mid;
  }
}

console.log(data[lo]);
console.log(search);
console.log(data[lo+1]);

.as-console-wrapper{top:0;max-height:100%!important}

Answer 2

var pos = data.indexOf(data.find(function(obj) { 
    var value = (obj.moment.split(":")[0]*60) + (obj.moment.split(":")[1]*1)
    var key =(search.split(":")[0]*60) + (search.split(":")[1]*1);
    return (key < value);
   }));

pos = pos >= 0 ? pos : data.length

data.splice(pos, 0, {moment:search, otherProp:"something", somethingMore: "someelse"});

这行得通。

在 Javascript 中的对象数组中进行高效搜索

Efficient search in a array of obj in Javascript

javascript

algorithm

binary-search