C++で等差数列から欠けている要素を二分探索で効率的に見つける方法

問題の概要

等差数列の要素が順番に並んだ配列が与えられますが、そのうち1つの要素が欠けています。この欠けている要素を見つけるのが本記事の目的です。

例えば、配列が arr = [2, 4, 8, 10, 12, 14] の場合、公差は2であり、6が欠けているため、出力は 6 となります。

アルゴリズムのポイント:二分探索の活用

この問題は二分探索を使うことで、O(log n)の計算量で効率的に解くことができます。基本的な考え方は以下のとおりです。

• まず配列の中央の要素に着目します。
• 中央の要素とその次の要素の差が、公差(diff)と一致しているかどうかを確認します。
• 一致しない場合、欠けている要素はインデックス mid と mid + 1 の間に存在します。
• 中央の要素が等差数列の理論上の値(初項 + mid × 公差)と一致する場合、欠けている要素は右半分にあります。一致しない場合は左半分にあります。

この性質を利用して探索範囲を半分ずつ絞り込んでいくことで、高速に欠落要素を特定できます。

C++による実装例

#include <iostream>
using namespace std;
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);
}

実行結果

The missing element is: 6

まとめ

等差数列の性質「任意の位置の値 = 初項 + インデックス × 公差」を活用し、二分探索で探索範囲を半分ずつ絞り込むことで、線形探索のO(n)よりも高速なO(log n)で欠けている要素を見つけることができます。公差の計算方法と中央要素との差の比較が、このアルゴリズムの核心となるポイントです。