C++有一个已经排列好数组,今输入一个数,要求按照原来排序规律将他插入到数组中
时间: 2023-04-12 19:01:07 浏览: 81
可以使用二分查找法来找到新数应该插入的位置,然后将其插入到数组中。具体实现可以参考以下代码:
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] > target) right = mid - 1;
else left = mid + 1;
}
return left;
}
void insert(int arr[], int n, int target) {
int pos = binarySearch(arr, n, target);
for (int i = n - 1; i >= pos; i--) {
arr[i + 1] = arr[i];
}
arr[pos] = target;
}
其中,binarySearch 函数用于找到新数应该插入的位置,insert 函数用于将新数插入到数组中。
相关问题
C++实现有一个已经排列好数组,今输入一个数,要求按照原来排序规律将他插入到数组中
可以使用二分查找法找到插入位置,然后将该数插入到数组中即可。以下是示例代码:
```c
int insert(int arr[], int n, int x) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
for (int i = n - 1; i >= left; i--) {
arr[i + 1] = arr[i];
}
arr[left] = x;
return n + 1;
}
```
其中,arr为已排好序的数组,n为数组长度,x为要插入的数。函数返回插入后的数组长度。
c++已知从小到大排列的5个数(38,100,312,531,812),再输入一个数,要求按原来的规律将它插入该数组中。
可以使用插入排序的思路来解决这个问题。
具体步骤如下:
1. 定义一个大小为6的数组 arr,将给定的5个数存入其中。
2. 输入一个数 num。
3. 从数组的最后一个位置开始,依次将数组中的元素向后移动,直到找到第一个比 num 小的元素或者遍历到数组的第一个位置。
4. 将 num 插入到刚才找到的位置之后。
5. 输出插入后的数组。
代码实现如下:
```c++
#include <iostream>
using namespace std;
int main() {
int arr[6] = {38, 100, 312, 531, 812}; // 原始数组
int num; // 待插入的数
cout << "请输入一个数:" << endl;
cin >> num;
int i = 4; // 从数组的最后一个位置开始遍历
while (i >= 0 && arr[i] > num) { // 找到第一个比 num 小的元素
arr[i + 1] = arr[i]; // 将元素向后移动
i--;
}
arr[i + 1] = num; // 将 num 插入到刚才找到的位置之后
cout << "插入后的数组为:" << endl;
for (int j = 0; j < 6; j++) { // 输出插入后的数组
cout << arr[j] << " ";
}
cout << endl;
return 0;
}
```
输出结果为:
```
请输入一个数:
200
插入后的数组为:
38 100 200 312 531 812
```