本文介绍在元素持续插入的动态场景下，如何用 javascript 高效维护数组中位数，重点讲解基于有序插入的轻量级实现，并对比其时间复杂度与适用边界。
本文介绍在元素持续插入的动态场景下，如何用 javascript 高效维护数组中位数，重点讲解基于有序插入的轻量级实现，并对比其时间复杂度与适用边界。
在流式数据或实时统计场景中（如监控指标、滑动窗口分析），需频繁向集合添加新数值并快速获取当前中位数。此时，若每次查询都对全量数组排序（O(n log n)），性能将随数据增长急剧恶化。理想方案应兼顾插入效率与查询常数时间——而平衡二叉搜索树或双堆（max-heap + min-heap）虽理论最优（O(log n) 插入 + O(1) 查询），但在 JavaScript 中缺乏原生支持，需手动实现或依赖第三方库，工程成本较高。
对于中等规模数据（如 维持一个始终有序的数组，并通过二分查找定位插入位置，再用 splice 完成插入。该方法将插入复杂度控制在 O(n)（主要开销在数组移位），但因省去了排序调用和额外数据结构维护，实际性能稳定、代码可读性强、调试直观。
以下是一个完整、可直接运行的 Median 类实现：
class Median {
arr = [];
insert(i) {
// 二分查找插入位置：找到第一个 >= i 的索引
let left = 0;
let right = this.arr.length;
while (left < right) {
const mid = (left + right) >>> 1; // 无符号右移，等价于 Math.floor((left+right)/2)
if (this.arr[mid] < i) {
left = mid + 1;
} else {
right = mid;
}
}
this.arr.splice(left, 0, i); // 在 left 处插入 i
}
get median() {
const len = this.arr.length;
if (len === 0) return undefined;
const mid = Math.floor(len / 2);
if (len % 2 === 1) {
return this.arr[mid]; // 奇数长度：取中间元素
} else {
return (this.arr[mid - 1] + this.arr[mid]) / 2; // 偶数长度：取中间两数均值
}
}
}
// 使用示例
const m = new Median();
[2, 8, 8, -2, 19].forEach(num => m.insert(num));
console.log(m.median); // 输出: 8✅ 关键设计说明：
立即学习“Java免费学习笔记（深入）”；
-
insert()使用闭区间二分查找（left到right，含right），确保在重复值中插入到最左侧合法位置，保持稳定性； -
>>> 1替代Math.floor((l+r)/2)提升整数运算效率，避免浮点误差； -
mediangetter 根据数组长度奇偶性自动选择单值或双值平均，逻辑清晰无歧义。
⚠️ 注意事项与优化建议：
- 时间复杂度：单次
insert为 O(n)（二分查找 O(log n) + 数组插入 O(n)），适合低频插入或中小规模数据；若插入频次高（如每秒千次以上），建议升级为双堆结构（可用tinyqueue或自定义最小/最大堆）； - 内存友好：不引入额外对象或递归调用，适用于嵌入式环境或内存受限场景；
- 扩展性提示：如需支持删除操作，可扩展
remove(value)方法，同样基于二分查找定位后splice删除，但需注意重复值处理策略。
综上，该方案以“可理解性”与“实用性”优先，在多数业务场景中提供了优雅的工程解——不必过早优化，但需清楚其边界：当数据量突破万级或吞吐要求严苛时，应平滑迁移到基于堆的 O(log n) 解法。
