C++で重複を含むソート済み配列のイコールポイント（中間点）を検索する方法

問題の概要

ソート済みの配列（要素数 n）が与えられたとき、「その要素より小さい要素の数」と「その要素より大きい要素の数」が等しくなる要素（イコールポイント）が配列内に存在するかどうかを調べる問題を考えます。イコールポイントが複数存在する場合は、最初に出現するインデックスを返し、該当する要素が存在しない場合は -1 を返します。

例えば、配列 A = [1, 1, 2, 3, 3, 3, 3, 3] の場合、イコールポイントはインデックス 2 の要素 A[2] = 2 です。この要素より小さい要素は「1」のみ（1個）、大きい要素は「3」のみ（1個）で、その数が等しいためです。

アルゴリズムの考え方

この問題は、重複を除去した要素のインデックスを格納する補助配列を作成することで効率的に解けます。ソート済み配列を先頭から走査し、隣接する要素と値が異なる位置だけを記録していきます。走査が完了した後、重複を除いた要素の個数を確認します。

• 個数が偶数の場合：イコールポイントは存在しないため -1 を返します。
• 個数が奇数の場合：補助配列の中央にある要素がイコールポイントとなります。

処理の手順

1. 配列を先頭から走査し、現在のインデックスを補助配列に記録します。
2. 隣接する要素が同じ値である限りインデックスを進め、重複をスキップします。
3. 走査終了後、補助配列のサイズが奇数なら中央のインデックスを、偶数なら -1 を返します。

C++での実装例

#include<iostream>
using namespace std;
int searchEqualPoint(int arr[], int n) {
    int aux_arr[n];
    int i = 0, aux_index = 0;
    while (i < n) {
        aux_arr[aux_index++] = i++;
        while (i<n && arr[i] == arr[i-1])
            i++;
    }
    return (aux_index & 1)? aux_arr[aux_index>>1] : -1;
}
int main() {
    int arr[] = {1, 1, 2, 3, 3, 3, 3, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    int index = searchEqualPoint(arr, n);
    if (index != -1)
        cout << "Equal Point is: " << arr[index];
    else
        cout << "No Equal Point exists";
}

実行結果

Equal Point is: 2

計算量

このアルゴリズムの時間計算量は O(n) で、配列を一度だけ走査すればよいため非常に効率的です。ただし、重複を除去したインデックスを保存する補助配列が必要なため、空間計算量は O(n) となります。