零起点学算法85——数组中插入一个数

题目描述：

给定一个有序数组和一个数，将这个数插入到数组中，并保证数组仍然有序。

输入格式：

第一行输入一个整数 n，表示数组的长度。

第二行输入 n 个整数，表示给定的有序数组。

第三行输入一个整数 x，表示要插入的数。

输出格式：

输出 n+1 个整数，表示插入新数后的数组。

输入样例：

5
1 3 4 6 8
5

输出样例：

1 3 4 5 6 8

算法1

(暴力枚举) $O(n)$

直接从头到尾遍历数组，找到第一个大于等于插入数的位置，然后将插入数插入到该位置。

时间复杂度

遍历一次数组，时间复杂度为 $O(n)$。

C++ 代码

算法2

(二分查找) $O(logn)$

由于数组是有序的，可以使用二分查找找到第一个大于等于插入数的位置，然后将插入数插入到该位置。

时间复杂度

二分查找的时间复杂度为 $O(logn)$。

C++ 代码