| 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 | }
|