基于二分查找实现有序日志数组时间范围的对数级过滤

问题1：undefined入参的处理合理性 #

原有处理存在两处明显缺陷：

• 逻辑运算符||会把0、NaN这类falsy有效值错误覆盖，比如用户要查从0毫秒开始的日志，会被误替换为Number.MIN_VALUE，不符合预期。正确应该用空值合并运算符??，仅在值为undefined/null时才替换。
• 对Number.MIN_VALUE的认知错误：它是JavaScript中可表示的最小正数值，不是最小负数。如果需要覆盖所有合法时间戳，应该替换为Number.MIN_SAFE_INTEGER，对应max替换为Number.MAX_SAFE_INTEGER。
• 额外优化：min和max都为undefined时，直接返回items.slice()即可，原有代码的slice(0, len-1)会丢弃数组最后一个元素，属于逻辑bug。

更优的处理逻辑：

if (min === undefined && max === undefined) {
  return items.slice(); // 直接返回全量拷贝，不丢失元素
}
min = min ?? Number.MIN_SAFE_INTEGER;
max = max ?? Number.MAX_SAFE_INTEGER;
// 增加参数合法性校验，min大于max直接返回空
if (min > max) return [];

问题2：二分查找上下界的实现 #

原有实现的compareFn同时判断min和max会增加边界查找复杂度，建议拆分为两个独立的查找逻辑：

1. 找左边界：第一个time >= min的元素下标
2. 找右边界：最后一个time <= max的元素下标
   如果左边界超过右边界，说明没有符合条件的元素，直接返回空。

当mid命中符合区间的元素时的处理逻辑：

• 如果是找左边界：说明还可能存在更早的符合条件的元素，把右指针移到mid-1，继续往左搜索
• 如果是找右边界：说明还可能存在更晚的符合条件的元素，把左指针移到mid+1，继续往右搜索
  循环结束后再校验最终的位置是否符合条件，返回对应值即可，全程不需要额外线性遍历，时间复杂度稳定为O(log n)。

另外注意mid计算必须取整，不能用浮点数作为数组下标，初始右指针应该是len-1而非len，避免数组越界。

完整修正后的代码 #

filterByTime(min?: number, max?: number): LogItem[] {
  const items = this.items;
  const len = items.length;
  if (len === 0) return [];

  // 全量返回场景
  if (min === undefined && max === undefined) {
    return items.slice();
  }

  const effectiveMin = min ?? Number.MIN_SAFE_INTEGER;
  const effectiveMax = max ?? Number.MAX_SAFE_INTEGER;

  if (effectiveMin > effectiveMax) return [];

  // 找左边界：第一个time >= effectiveMin的位置
  const lowerBound = this.binarySearchBound(
    (item) => item.time - effectiveMin, 
    true
  );
  // 左边界超出数组范围，或者左边界的time已经大于max，直接返回空
  if (lowerBound === -1 || items[lowerBound].time > effectiveMax) {
    return [];
  }

  // 找右边界：最后一个time <= effectiveMax的位置
  const upperBound = this.binarySearchBound(
    (item) => item.time - effectiveMax, 
    false
  );

  // slice是左闭右开，所以结束下标要+1
  return items.slice(lowerBound, upperBound + 1);
}

/**
 * @param compareFn 比较函数，返回负数：当前元素小于目标，正数：当前元素大于目标，0：等于目标
 * @param isLowerBound 是否找左边界
 */
binarySearchBound(compareFn: (a: LogItem) => number, isLowerBound: boolean): number {
  const items = this.items;
  const len = items.length;
  let left = 0;
  let right = len - 1;
  let result = -1;

  while (left <= right) {
    // 取整避免浮点数下标，同时规避大数相加溢出
    const mid = left + Math.floor((right - left) / 2);
    const compare = compareFn(items[mid]);

    if (compare < 0) {
      // 当前元素小于目标，往右找
      left = mid + 1;
    } else if (compare > 0) {
      // 当前元素大于目标，往左找
      right = mid - 1;
    } else {
      // 当前元素匹配，记录位置，继续往对应方向找更靠近边界的匹配项
      result = mid;
      if (isLowerBound) {
        // 找左边界就继续往左搜
        right = mid - 1;
      } else {
        // 找右边界就继续往右搜
        left = mid + 1;
      }
    }
  }

  return result;
}

内容的提问来源于stack exchange，提问作者Luke Vo