Javascript equivalent of equal_range in C++

Question

I'm new to Javascript, and I'm wondering if there are any existing Javascript libraries which contain binary search functionality similar to C++ equal_range? I wrote a quick implementation of what I'm looking for:

/*
 * Javascript version of C++ equal_range via lower_bound and upper_bound
 *
 * Input: The array A in ascending order and a target T
 * Output: The tightly bound indices [i, j] where A[i] <= T < A[j] if T exists in A
 * otherwise [-1, -1] is returned if T does not exist in A
 */

let lowerBound = (A, T) => {
    let N = A.length,
        i = 0,
        j = N - 1;
    while (i < j) {
        let k = Math.floor((i + j) / 2);
        if (A[k] < T)
            i = k + 1;
        else
            j = k;
    }
    return A[i] == T ? i : -1;
};

let upperBound = (A, T) => {
    let N = A.length,
        i = 0,
        j = N - 1;
    while (i < j) {
        let k = Math.floor((i + j + 1) / 2);
        if (A[k] <= T)
            i = k;
        else
            j = k - 1;
    }
    return A[j] == T ? j + 1 : -1;
};

let equalRange = (A, T) => {
    return [lowerBound(A, T), upperBound(A, T)];
};

Answer 1

The Google closure-library may be the closest library I've found so far:

https://google.github.io/closure-library/api/goog.array.html

Answer 2

Your code is incorrect, see attached comment regarding the incorrect return of -1 for any unfound element, when AFAIK -1 should never be returned (though provision appears to be made for such in the description, the demo code at https://en.cppreference.com/w/cpp/algorithm/lower_bound does not seem capable of returning -1 under any condition).

Therefore a more correct implementation would be:

function equalRange(array, value) {
  const lowerBoundIndex = lowerBound(array, value);
  const upperBoundIndex = upperBound(array, value);

  return [lowerBoundIndex, upperBoundIndex];
}

function lowerBound(array, value) {
  let low = 0;
  let high = array.length;

  while (low < high) {
    const mid = Math.floor((low + high) / 2);

    if (array[mid] < value) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }

  return low;
}

function upperBound(array, value) {
  let low = 0;
  let high = array.length;

  while (low < high) {
    const mid = Math.floor((low + high) / 2);

    if (array[mid] <= value) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }

  return low;
}

Example usage:

const sortedArray = [1, 2, 2, 3, 4, 4, 4, 5, 6];

const value1 = 4;
const range1 = equalRange(sortedArray, value1);
console.log(range1); // Output: [4, 7]

const value2 = 2;
const range2 = equalRange(sortedArray, value2);
console.log(range2); // Output: [1, 3]

const value3 = 7;
const range3 = equalRange(sortedArray, value3);
console.log(range3); // Output: [9, 9] (index beyond the end of the array)

In this example, equalRange takes a sorted array and a value as input. It uses the lowerBound and upperBound functions to find the lower bound and upper bound indices, respectively. It then returns a pair of indices representing the range of elements equal to the value. If the value is greater than all elements in the array, the function will return the index beyond the end of the array for both bounds.