C++で等差数列から欠けた要素を二分探索で見つける方法

等差数列の欠けている要素を見つける問題

等差数列の要素が順番に並んだ配列があるとします。ただし、そのうち1つの要素だけが欠けています。この欠けている要素を見つけるのが本記事の課題です。例えば、arr = [2, 4, 8, 10, 12, 14] という配列の場合、6が欠けているため、出力は6になります。

アルゴリズムの考え方：二分探索の活用

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

1. 配列の中央の要素（mid）に注目します。
2. 中央の要素とその隣の要素（mid + 1）の差が、公差（diff）と一致しているかどうかを確認します。
3. 差が公差と異なる場合、欠けている要素はインデックスmidとmid + 1の間に存在します。
4. 中央の要素が本来あるべき値（arr[0] + mid × diff）と一致している場合、欠けた要素は右半分にあります。一致しない場合は左半分にあります。

この探索を繰り返すことで、時間計算量O(log n)で欠けている要素を特定できます。

C++での実装例

#include <iostream>
using namespace std;
#define INT_MAX 999999
class Progression {
   public:
   int missingUtil(int arr[], int left, int right, int diff) {
      if (right <= left)
         return INT_MAX;
      int mid = left + (right - left) / 2;
      if (arr[mid + 1] - arr[mid] != diff)
         return (arr[mid] + diff);
      if (mid > 0 && arr[mid] - arr[mid - 1] != diff)
         return (arr[mid - 1] + diff);
      if (arr[mid] == arr[0] + mid * diff)
         return missingUtil(arr, mid + 1, right, diff);
      return missingUtil(arr, left, mid - 1, diff);
   }
   int missingElement(int arr[], int n) {
      int diff = (arr[n - 1] - arr[0]) / n;
      return missingUtil(arr, 0, n - 1, diff);
   }
};
int main() {
   Progression pg;
   int arr[] = {2, 4, 8, 10, 12, 14};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "The missing element is: " << pg.missingElement(arr, n)<<endl;
}

入力

[2,4,8,10,12,14]

出力

The missing element is: 6

コードのポイント

この実装で重要なのは、公差diffの求め方です。1つの要素が欠けているため、本来の要素数はn + 1個になります。そこで、末尾の要素から先頭の要素を引いた値をnで割ることで、正しい公差 (arr[n-1] - arr[0]) / n を算出できます。

また、再帰関数missingUtilでは次の3つのケースを処理しています。

• arr[mid + 1] - arr[mid] が公差と異なる場合：欠けた要素はmidの直後なので、arr[mid] + diff を返します。
• arr[mid] - arr[mid - 1] が公差と異なる場合：欠けた要素はmidの直前なので、arr[mid - 1] + diff を返します。
• それ以外の場合：中央の値が正しい位置の値と一致していれば右半分を、一致していなければ左半分を再帰的に探索します。

このように二分探索を応用することで、線形探索のO(n)に対してO(log n)と大幅に計算量を抑えられるのが大きな利点です。