C++でソート済み配列から欠落している1つの数値を見つける方法

この問題では、1からNまでの値が格納され、そのうち1つの値だけが欠落しているサイズNの配列 arr[] が与えられます。私たちのタスクは、ソートされた配列の中で欠落している唯一の数値を見つけることです。

具体例で問題を確認してみましょう。

入力:

arr[] = {1, 2, 3, 5, 6, 7}

出力:

4

上記の例では、配列には1〜7の値が含まれるはずですが、4が欠落しているため、出力は4となります。

解法1: 線形探索によるアプローチ

最もシンプルな解決策は、ソートされた配列を先頭から順番に走査する方法です。「i番目の要素は i + 1 になるはず」という性質（arr[i] = i + 1）を利用して、期待される値と実際の値が一致しない位置を見つければ、そこで欠落している数値を特定できます。

実装例

以下は、この解法の動作を示すC++プログラムです。

#include <iostream>
using namespace std;
int findMissingValArray(int arr[], int N){
    for(int i = 0; i < N; i++){
        if(arr[i] != (i+1))
            return (i+1);
    }
    return -1;
}
int main(){
    int arr[] = {1, 2, 3, 4, 6};
    int N = sizeof(arr)/sizeof(arr[0]);
    cout<<"配列の中で欠落している値は "<<findMissingValArray(arr, N)<<" です";
    return 0;
}

出力:

配列の中で欠落している値は 5 です

この方法の時間計算量は O(N) です。配列全体を一度走査するため、確実に答えを見つけられますが、要素数が多い場合には効率が低下します。

解法2: 二分探索によるアプローチ

配列がソート済みであることを活かせば、二分探索を使ってより効率的に解くことができます。探索範囲の中央（mid）にある値を確認し、次のように判定を行います。

• arr[mid] が期待値 (mid + 1) と異なり、かつ直前の要素 arr[mid - 1] が mid と一致している場合 → 欠落している値は mid + 1 と特定できます。
• arr[mid] が期待値と異なる場合 → 欠落箇所は左半分にあるため、探索範囲を左側に狭めます。
• arr[mid] が期待値と一致している場合 → 欠落箇所は右半分にあるため、探索範囲を右側に狭めます。

実装例

以下は、二分探索を用いた解法のC++プログラムです。

#include <iostream>
using namespace std;
int findMissingValArray(int arr[], int N){
    int s = 0, e = N - 1;
    while (s <= e) {
        int mid = (s + e) / 2;
        if (arr[mid] != mid + 1 && arr[mid - 1] == mid)
            return (mid + 1);
        if (arr[mid] != (mid + 1))
            e = (mid - 1);
        else
            s = (mid + 1);
    }
    return -1;
}
int main(){
    int arr[] = {1, 2, 3, 4, 6};
    int N = sizeof(arr)/sizeof(arr[0]);
    cout<<"配列の中で欠落している値は "<<findMissingValArray(arr, N)<<" です";
    return 0;
}

出力:

配列の中で欠落している値は 5 です

この方法の時間計算量は O(log N) であり、線形探索よりも大幅に高速です。特に大規模な配列を扱う場合に有効なアプローチといえます。

まとめ

ソート済み配列から欠落している数値を見つけるには、線形探索（O(N)）と二分探索（O(log N)）の2つの主な方法があります。配列がソートされているという前提条件があるため、二分探索を活用することで計算量を抑え、効率的に答えを求めることができます。