二分插入通过二分查找快速定位插入位置，将查找降为O(log n)，虽移动仍为O(n)，但显著减少比较次数，适用于小规模或高频插入场景；其核心是复用插入索引left实现排名计算、去重判断与范围操作。
在数组上实现高效有序集合，核心在于控制插入成本。普通线性查找插入位置需 O(n) 时间，而结合二分查找定位、后移插入的“二分插入”策略，可将查找步骤压缩至 O(log n)，整体仍为 O(n)（受限于元素移动），但实际比较次数大幅下降，尤其适合小规模或高频插入+低频修改场景。
二分插入的本质逻辑
它不改变数组插入必须移动后续元素这一物理约束，而是聚焦优化“找位置”环节：在已排序的前 i 个元素中，用二分法快速锁定新值应插入的索引 j，避免从右往左逐个比对。
- 前提：插入前，
a[0..i-1]已升序排列 - 目标：确定
a[i]在a[0..i]中的最终下标 - 关键动作：二分过程返回的是“第一个 ≥ 目标值”的位置（即插入点），不是查找是否存在
手写二分插入函数（Java 示例）
以下是一个清晰、边界安全的实现，支持重复元素且保持稳定：
public void insertSorted(int[] arr, int size, int value) {
// 1. 二分查找插入位置：left 最终即为插入索引
int left = 0, right = size;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < value) {
left = mid + 1;
} else {
right = mid;
}
}
// 2. 后移：从末尾开始，把 [left, size-1] 整体右移一位
for (int i = size; i > left; i--) {
arr[i] = arr[i - 1];
}
// 3. 赋值
arr[left] = value;
}注意：size 是当前有效长度，调用时需确保 arr.length > size；该函数不扩容，仅维护逻辑有序性。
实战中如何用好这个“变量”
所谓“优化变量”，不是指某个 magic 变量，而是指你在设计数据结构时，把 插入位置索引 作为关键中间结果来复用和验证：
- 可直接用于后续操作：比如插入后立刻获取其排名（就是
left + 1）、判断是否为最小/最大值（left == 0或left == size） - 可用于去重控制：若要求集合无重复，插入前检查
arr[left] == value，成立则跳过插入 - 可扩展为范围操作基础：多次调用该函数插入一批数，再统一做合并或统计，比逐个 sort + dedup 更可控
与标准库的对比与取舍
Java 的 Arrays.binarySearch() 返回负值表示插入点（按公式 -(insertionPoint) - 1），需转换；而自己实现能完全掌控行为（如重复处理、边界语义）。但在生产环境，若只是临时维护小集合，用 TreeSet 更省心；只有当你需要数组连续内存、避免对象封装开销、或嵌入底层协议层时，手动二分插入才真正体现价值。
