中文
devexamples

Lower and Upper Bound Binary Search

Find the first and last insertion points for a value in a sorted array with a custom comparator, then count duplicates in logarithmic time.

JavascriptData Integrity

Code

snippet
export function lowerBound(array, target, compare = defaultCompare) {
  assertArray(array);
  let low = 0;
  let high = array.length;
  while (low < high) {
    const mid = (low + high) >>> 1;
    if (compare(array[mid], target) < 0) low = mid + 1;
    else high = mid;
  }
  return low;
}

export function upperBound(array, target, compare = defaultCompare) {
  assertArray(array);
  let low = 0;
  let high = array.length;
  while (low < high) {
    const mid = (low + high) >>> 1;
    if (compare(array[mid], target) <= 0) low = mid + 1;
    else high = mid;
  }
  return high;
}

export function countOccurrences(array, target, compare) {
  return upperBound(array, target, compare) - lowerBound(array, target, compare);
}

function defaultCompare(left, right) {
  return left < right ? -1 : left > right ? 1 : 0;
}

function assertArray(array) {
  if (!Array.isArray(array)) throw new TypeError("array must be an array");
}

const scores = [10, 20, 20, 20, 35, 50];
console.log(lowerBound(scores, 20));
console.log(upperBound(scores, 20));
console.log(countOccurrences(scores, 20));
console.log(lowerBound(scores, 25));

Related Examples