【C++】昇順ソート済みの連続数列から欠落している要素を二分探索で効率的に見つける方法

概要

互いに異なる n 個の整数が格納された配列 array[] が与えられます。要素は昇順に並んでいますが、そのうち1つだけが欠落しています。この記事では、その欠落要素を効率よく特定するアルゴリズムを、原理からサンプルコードまでわかりやすく解説します。

入出力例

例1:欠落要素がある場合

入力:

array[] = {1, 2, 3, 4, 5, 6, 7, 9}

出力:

8

例2:負の数を含む場合

入力:

array[] = {-4, -2, -1, 0, 1, 2}

出力:

-3

例3:欠落要素がない場合

入力:

array[] = {1, 2, 3, 4}

出力:

-1

すべての要素が連続している場合は -1 を返します。

解法のアプローチ

基本原理:「整合性」のチェック

この手法の鍵となるのは、「各要素とそのインデックスの差は、常に先頭要素 array[0] と等しくなる」という性質です。この性質が崩れた箇所(不整合)を探すことで、欠落位置を絞り込めます。

具体例:

• A[] = {1, 2, 3, 4, 5} → 整合性あり(すべての要素で「値 − インデックス = 1」)
• B[] = {201, 202, 203, 204} → 整合性あり(すべての要素で「値 − インデックス = 201」)
• C[] = {1, 2, 3, 5, 6} → 整合性なし(C[3] − 3 ≠ C[0]、つまり 5 − 3 ≠ 1)

不整合の有無を判定することで、配列全体を線形に走査する代わりに、毎回半分だけを調べればよくなり、計算量を O(log N) に抑えられます。

アルゴリズムの手順

1. 中央の要素を求め、その整合性を確認します。

2. 中央の要素が整合性を持つ場合: 中央の要素とその次の要素の差が 1 より大きいか(array[mid + 1] - array[mid] > 1)を確認します。

   • 差が 1 より大きい場合 → array[mid] + 1 が欠落要素です。
   • それ以外の場合 → 中央より右半分を新たな探索範囲とし、手順1へ戻ります。

3. 中央の要素が不整合の場合: 中央の要素とその直前の要素の差が 1 より大きいか(array[mid] - array[mid - 1] > 1)を確認します。

   • 差が 1 より大きい場合 → array[mid] - 1 が欠落要素です。
   • それ以外の場合 → 中央より左半分を新たな探索範囲とし、手順1へ戻ります。

C++による実装例

// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// 欠落要素を返す関数
int findMissing(int array[], int n1){
    int low = 0, high = n1 - 1;
    int mid1;
    while (high > low){
        mid1 = low + (high - low) / 2;
        // 中央の要素が整合性を持つか確認
        if (array[mid1] - mid1 == array[0]){
            // 中央までは不整合なし
            // 欠落要素が中央の直後にある場合
            if (array[mid1 + 1] - array[mid1] > 1)
                return array[mid1] + 1;
            else{
                // 右半分へ移動
                low = mid1 + 1;
            }
        }
        else{
            // 不整合が見つかった場合
            // 欠落要素が中央の直前にある場合
            if (array[mid1] - array[mid1 - 1] > 1)
                return array[mid1] - 1;
            else{
                // 左半分へ移動
                high = mid1 - 1;
            }
        }
    }
    // 欠落要素が見つからなかった場合
    return -1;
}
// Driver code
int main(){
    int array[] = { -9, -8, -6, -5, -4, -3, -2, -1, 0 };
    int n1 = sizeof(array)/sizeof(array[0]);
    cout <<"The Missing Element:" <<(findMissing(array, n1));
}

実行結果

The Missing Element:-7

計算量について

• 時間計算量: O(log N) — 二分探索により、各ステップで探索範囲が半分になります。
• 空間計算量: O(1) — 追加のメモリは定数個の変数のみで済みます。

このように、単純な線形探索(O(N))と比べて、大きな配列でも高速に欠落要素を特定できるのがこの手法の大きな利点です。