javascript select range from ordered array of objects

Question

Let's assume we have a large array of objects, ordered by a specific field range_id:

const points = [
{"x":3,"y":4,"range_id"=0},
{"x":7,"y":9,"range_id"=0},
{"x":5,"y":1,"range_id"=1},
{"x":2,"y":6,"range_id"=1},
{"x":12,"y":0,"range_id"=2},
...
{"x":73,"y":61,"range_id"=5000},
{"x":21,"y":87,"range_id"=5000},
];

now I would like to do the equivalent of

points.filter(pt => pr.range_id=1);

But since the array is supposed to be large, I want to use a function that is aware that the array is sorted by range_id which acts like an index.

In SQL, there would be an index on range_id.

In C++20, we could use ranges::equal_range().

How can it be done in Javascript ?

Answer 1

If the data is sorted you can do a binary search which runs in O(log(N)) time.

make two searches, one to find the start of the range, one to find the end.

// supposed to find the index of the first element that matches the predicate.
// expects that ALL elements after that also match!
function binarySearch(array, predicate) {
  let lo = 0, hi = array.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (predicate(array[mid], mid, array)) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  return lo;
}


// generate some data
var data = [...Array(10).keys()]
  .flatMap(id => Array(Math.floor(Math.random() * 5 + 1)).fill(id))
  .map((range_id, index) => ({ range_id, index }));

const search = 4;
// find the start of the range
const start = binarySearch(data, item => item.range_id >= search);
// find the end of the range
const end = binarySearch(data, item => item.range_id > search);

console.log(data);
console.log(start,end);
console.log(data.slice(start,end));