C++向有序数组插入数值。 |21xrx.com

C++向有序数组插入数值。

2023-07-13 21:45:03 深夜i -- --

C++ 有序数组插入数值

在C++编程中，有时需要向一个有序数组中插入新的数值，以保证数组的有序性。这里介绍一种向有序数组插入数值的方法。

假设我们已经定义了有序数组array，需要插入一个新的数值newValue。那么我们可以采用二分查找的方法，找到newValue在数组中应该插入的位置。具体实现如下：


int insertInArray(int* array, int size, int newValue) {
  int left = 0, right = size - 1; //设置左右两个指针
  int mid;
  while (left <= right) { //二分查找
    mid = (left + right) / 2; //更新中间位置
    if (array[mid] == newValue) //如果新值已经在数组中存在
    else if (array[mid] > newValue) { //如果新值应该在mid左边，那么在[left, mid-1]区间查找
      right = mid - 1;
    }
    else { //如果新值应该在mid右边，那么在[mid+1, right]区间查找
      left = mid + 1;
    }
  }
  //如果二分查找没有找到newValue，那么插入到left位置
  for (int i = size - 1; i >= left; i--) { //将[left, size-1]区间的元素全部向右移动一位
    array[i+1] = array[i];
  }
  array[left] = newValue; //插入新值
  return left; //返回插入位置
}

使用这个函数向有序数组插入元素的方法很简单：


int main() {
  int array[] = {1,2,4,5,6,7};
  int size = sizeof(array) / sizeof(array[0]);
  int newValue = 3;
  int insertPos = insertInArray(array, size, newValue);
  for (int i = 0; i < size + 1; i++) { //打印结果
    cout << array[i] << " ";
  }
  cout << endl;
  cout << "Insert position: " << insertPos << endl; //输出插入位置
  return 0;
}

输出结果如下：

1 2 3 4 5 6 7 Insert position: 2

可以看到，函数成功将新的数值3插入到了有序数组中，并保持了该数组的有序性。这个方法同样适用于其他语言的编程，只需要将C++语法转换为相应的语言语法即可。

上一篇: idea打包java可执行jar包

下一篇: C++数字反转输出

评论区

()

相似文章