1 | // Port of lower_bound from https://en.cppreference.com/w/cpp/algorithm/lower_bound
|
2 | // Used to compute insertion index to keep queue sorted after insertion
|
3 | export default function lowerBound(array, value, comparator) {
|
4 | let first = 0;
|
5 | let count = array.length;
|
6 | while (count > 0) {
|
7 | const step = Math.trunc(count / 2);
|
8 | let it = first + step;
|
9 | if (comparator(array[it], value) <= 0) {
|
10 | first = ++it;
|
11 | count -= step + 1;
|
12 | }
|
13 | else {
|
14 | count = step;
|
15 | }
|
16 | }
|
17 | return first;
|
18 | }
|