在Java里有10个数,已经按从大到小的顺序排序,输人一个数,将它插人到原有 数列中并保持从大到小的顺序不变,输出该数插人的位置。
时间: 2024-10-10 13:04:57 浏览: 32
java-插入排序.rar
在Java中,如果你有一个已排序的数组(从大到小)并且需要插入一个新的数,同时保持数组的降序排列,你可以采用二分查找法来确定插入的位置。以下是基本步骤:
1. 初始化两个指针,`low` 表示数组的起始索引(0),`high` 表示数组的结束索引减一。
2. 使用 while 循环,当 `low <= high` 时继续循环:
a. 计算中间索引 `mid`,通常是 `(low + high) / 2`。
b. 比较新数 `num` 和数组中间的数 `array[mid]`。如果 `num` 大于中间数,说明应该在中间数右侧的子数组中查找,更新 `low = mid + 1`;如果 `num` 小于等于中间数,说明应该在中间数左侧的子数组中查找,更新 `high = mid - 1`。
3. 当找到 `low` 和 `high` 相等时,`low` 所对应的索引就是插入点,因为数组已经是有序的,所以在 `low` 位置之前的所有元素都比 `num` 小。
以下是一个简单的Java代码实现:
```java
public int insertPosition(int[] array, int num) {
int low = 0;
int high = array.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (array[mid] < num) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
// 示例:
int[] array = {9, 8, 7, 6, 5};
int num = 10;
int position = insertPosition(array, num); // 返回4,因为10应插入在5之后
```
阅读全文