在C ++中搜索插入位置

假设我们有一个排序后的数组arr和一个目标值，我们必须在找到目标时找到索引。如果不存在，则返回按顺序插入索引的位置的索引。

因此，如果输入类似于[1,3,4,6,6]，而target = 5，则输出将为3，因为我们可以在索引3处插入5，所以数组将为[1,3， 4,5,6,6]

为了解决这个问题，我们将按照以下步骤操作：

• n：= A的大小

• 如果n <1，则-

• 返回0

• 低：= 0，高：= n-1

• 当低<=高时，执行-

• 低：=中+ 1，pos：=中+ 1

• 高：=中-1，pos：=中

• 返回中

• 中：=低+（高-低）/ 2

• 如果A [mid]与目标相同，则-

• 否则，当A [mid]>目标时，则-

• 除此以外

• 返回位置

例 

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int searchInsert(vector<int>& A, int target) {
      int n = A.size();
      if(n < 1) {
         return 0;
      }
      int low = 0;
      int high = n-1;
      int mid;
      int pos;
      while(low <= high) {
         mid = low + (high-low)/2;
         if(A[mid] == target) {
            return mid;
         }
         else if(A[mid] > target) {
            high = mid - 1;
            pos = mid;
         }
         else {
            low = mid + 1;
            pos = mid + 1;
         }
      }
      return pos;
   }
};
main(){
   Solution ob;
   vector<int&g; v = {1,3,4,6,6};
   cout << (ob.searchInsert(v,5));
}

输入值

{1,3,4,6,6},5

输出结果

3