【C++】配列内に「全要素の合計の半分」と等しい要素が存在するか判定する方法

この記事では、ソート済みの重複なし整数配列 arr が与えられたとき、その配列の中に「全要素の合計値の半分」に等しい要素が存在するかどうかを判定する問題を解説します。

問題の概要

配列 arr[] から、次の条件を満たす要素 x を見つけることが目的です。

配列全体の要素の合計 = 2 × x（つまり、x は合計値のちょうど半分）

具体例で理解しよう

入力： arr[] = {2, 4, 5, 6, 7}

出力： No（該当する要素なし）

解説：

合計 = 2 + 4 + 5 + 6 + 7 = 24

24 の半分は 12 ですが、配列内に 12 という要素は存在しないため、該当する要素はありません。

解法のアプローチ

この問題を解くには、配列の全要素の合計を求め、その半分に一致する要素が配列内に存在するかを確認するだけです。

アルゴリズムの手順

ステップ1： 配列の全要素の合計値を求める。

ステップ2： 合計値が奇数の場合、半分の値が整数にならないため、-1 を返して終了する。

ステップ3： 合計値が偶数の場合、「x × 2 = 合計値」を満たす要素 x を探す。

ステップ4： 要素が見つかった場合は、その要素の値を返す。

ステップ5： 見つからなかった場合は、-1 を返す。

なお、配列がソート済みであるため、要素の探索には効率的な二分探索（バイナリサーチ）を利用できます。二分探索を使えば、線形探索の O(n) に対して O(log n) の時間計算量で高速に検索できます。

C++による実装例

#include <iostream>
using namespace std;

int checkForElement(int array[], int n) {

    int arrSum = 0;
    for (int i = 0; i < n; i++)
        arrSum += array[i];

    // 合計が奇数なら半分の要素は存在しない
    if (arrSum % 2)
        return -1;

    // 二分探索で合計の半分に等しい要素を探す
    int start = 0;
    int end = n - 1;
    while (start <= end)
    {
        int mid = start + (end - start) / 2;
        if ( ( 2 * array[mid] ) == arrSum)
            return array[mid];
        else if (( 2 * array[mid] ) > arrSum)
            end = mid - 1;
        else
            start = mid + 1;
    }

    return -1;
}

int main() {

    int array[] = { 4, 5, 6, 7, 9 };
    int n = sizeof(array) / sizeof(array[0]);
    int x = checkForElement(array, n);
    if(x != -1)
        cout<<"Element found, value is "<<x;
    else
        cout<<"Element not found!";
    return 0;
}

実行結果

Element not found!

コードのポイント

• まずループで配列の合計値を計算し、奇数なら即座に -1 を返して無駄な探索を省いています。
• 二分探索では 2 * array[mid] と合計値を比較することで、オーバーフローや割り算の誤差を避けながら安全に判定できます。
• この実装の時間計算量は合計計算の O(n) が支配的となり、探索部分は O(log n) で非常に効率的です。