1. 概述
数组在编程中无处不在，插入和删除元素是基础操作。将数字插入已排序数组是这类操作的典型场景，需要特别注意效率问题。
2. 问题引入
要高效插入数字到已排序数组，核心是减少位置移动和比较次数。我们可以通过二分查找快速定位插入位置，然后只移动必要的元素。举个栗子：
int[] sortedArray = new int[] { 4, 55, 85, 100, 125 };
现在要插入数字90，最终结果应该是：
int[] expcetedArray = new int[] { 4, 55, 85, 90, 100, 125 };
关键点在于：
- ✅ 用二分查找快速定位插入位置（85和100之间）
- ✅ 只移动90之后的元素（100和125）
- ❌ 避免从头遍历整个数组
3. 解决方案
实现分两步走：二分查找定位 + 元素右移腾位。代码实现如下：
public static int[] insertInSortedArray(int[] arr, int numToInsert) {
int index = Arrays.binarySearch(arr, numToInsert);
if (index < 0) {
index = -(index + 1);
}
int[] newArray = new int[arr.length + 1];
System.arraycopy(arr, 0, newArray, 0, index);
newArray[index] = numToInsert;
System.arraycopy(arr, index, newArray, index + 1, arr.length - index);
return newArray;
}
关键逻辑解析：
二分查找定位
Arrays.binarySearch()返回插入位置：- 找到元素时返回正索引
- 未找到时返回
-(插入点 + 1) - 所以负值需要转换：
index = -(index + 1)
高效数组复制
使用System.arraycopy()避免手动循环：- 第一次复制：插入点前的元素（0到index-1）
- 插入新元素
- 第二次复制：插入点后的元素（右移一位）
测试验证
用JUnit验证逻辑：
@Test
void givenSortedArray_whenElementInserted_thenArrayRemainsSorted() {
int[] sortedArray = new int[] { 4, 55, 85, 100, 125 };
int[] expcetedArray = new int[] { 4, 55, 85, 90, 100, 125 };
int valueToInsert = 90;
int[] resultArray = insertInSortedArray(sortedArray, valueToInsert);
assertThat(expcetedArray).isEqualTo(resultArray);
}
⚠️ 扩展提示：此方案同样适用于包装类型数组（Integer[], Double[]等），因为Arrays.binarySearch()和System.arraycopy()都支持对象数组。
4. 时间复杂度
算法复杂度分析：
- 二分查找：
O(log n) - 元素移动：
O(n)（最坏情况需移动所有元素） - 整体复杂度：
O(n)
虽然二分查找很快，但数组元素移动仍是瓶颈。如果频繁插入，建议考虑使用LinkedList或TreeSet等数据结构。
5. 总结
在Java中高效插入已排序数组的核心技巧：
- 二分查找快速定位插入点
- 批量复制代替逐个移动元素
- 注意边界处理（特别是
binarySearch的返回值转换）
完整代码示例已上传至GitHub仓库，可直接参考使用。