Java有序数组插入整数：二分查找算法实现

Java有序数组插入整数：二分查找算法实现

给定一个包含 n (n<=100) 个整数的数组，这些整数已经按照从小到大顺序排列好。现在需要另外给出一个整数 x，将其插入到该序列中，并使新的排序仍然有序。

思路

可以使用二分查找的方法找到新数应该插入的位置，然后将其插入到该位置。具体步骤如下：

1. 使用二分查找方法找到新数应该插入的位置，可以使用递归或者循环的方式实现。
2. 找到位置之后，将该位置及其之后的所有数向后移动一位，空出该位置。
3. 将新数插入到该位置。
4. 输出插入后的序列。

代码实现

以下是使用循环的方式实现二分查找和插入的代码，其中 nums 为原序列，n 为原序列的长度，x 为待插入的数：

int left = 0, right = n - 1;
int mid;
while (left <= right) {
    mid = (left + right) / 2;
    if (nums[mid] == x) {
        break;
    } else if (nums[mid] > x) {
        right = mid - 1;
    } else {
        left = mid + 1;
    } 
}
if (nums[mid] < x) {
    mid++;
}
for (int i = n - 1; i >= mid; i--) {
    nums[i + 1] = nums[i];
}
nums[mid] = x;
for (int i = 0; i <= n; i++) {
    System.out.print(nums[i] + " ");
}

使用递归的方式实现二分查找和插入的代码类似，可以自行尝试实现。