C++で挿入位置を検索する方法｜二分探索による実装を解説

ソート済み配列 arr とターゲット値が与えられたとき、ターゲットが配列内に存在する場合はそのインデックスを返します。存在しない場合は、順序を保ったまま挿入したと仮定した場合の挿入位置（インデックス）を返します。

例えば、入力が [1,3,4,6,6]、ターゲットが 5 の場合、出力は 3 になります。インデックス 3 に 5 を挿入すると、配列は [1,3,4,5,6,6] となるためです。

解法のアプローチ（二分探索）

この問題は、二分探索（バイナリサーチ）を使うことで O(log n) の計算量で効率的に解くことができます。手順は以下の通りです。

• n := A のサイズとする

• n < 1 の場合は 0 を返す

• low := 0、high := n - 1 で初期化する

• low <= high の間、以下を繰り返す

  • mid := low + (high - low) / 2 とする

  • A[mid] がターゲットと等しい場合：mid を返す

  • A[mid] がターゲットより大きい場合：high := mid - 1、pos := mid とする

  • それ以外の場合：low := mid + 1、pos := mid + 1 とする

• ループ終了後、pos を返す

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#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;
   }
};
int main(){
   Solution ob;
   vector<int> v = {1,3,4,6,6};
   cout << (ob.searchInsert(v,5));
   return 0;
}

入力

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

出力

3

計算量について

このアルゴリズムは、探索範囲を毎回半分に絞り込んでいくため、時間計算量は O(log n) となります。また、追加のメモリを使用しないため、空間計算量は O(1) です。ソート済み配列に対する挿入位置の検索において、先頭から順に調べる線形探索（O(n)）よりもはるかに高速に動作する点が大きなメリットです。