C++で挿入位置を検索

ソートされた配列arrとターゲット値があるとすると、ターゲットが見つかったときにインデックスを見つける必要があります。それが存在しない場合は、順番に挿入された場合のインデックスを返します。

したがって、入力が[1,3,4,6,6]のようで、target =5の場合、インデックス3に5を挿入できるため、出力は3になり、配列は[1,3、 4,5,6,6]

これを解決するために、次の手順に従います-

• n：=Aのサイズ

• n <1の場合、-

  • 0を返す

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

• 低い<=高い間、実行-

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

  • A [mid]がターゲットと同じ場合、-

    • 途中で戻る

  • それ以外の場合、A [mid]>ターゲットの場合、-

    • high：=mid-1、pos：=mid

  • それ以外の場合

    • low：=mid + 1、pos：=mid + 1

• 戻り値

例

理解を深めるために、次の実装を見てみましょう-

#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