C++で二分探索を使ってソート済み配列内の一意の要素を見つける方法

ソート済み配列から一度だけ現れる要素を検索する

ソート済みの配列Aがあるとします。すべての要素は2回ずつ現れますが、1つの要素だけが1回しか現れません。この一意の要素を見つける必要があります。例えば、配列が [1, 1, 3, 3, 4, 4, 5, 6, 6, 7, 7, 9, 9] の場合、求める要素は5です。

この問題は、二分探索（バイナリサーチ）のアプローチを用いて効率的に解決できます。一意の要素より前の部分では、各要素の最初の出現位置が偶数インデックス（0, 2, 4, ...）に、2回目の出現位置が奇数インデックス（1, 3, 5, ...）にあります。しかし、一意の要素より後ろではこのパターンが逆転し、最初の出現が奇数インデックスに、2回目の出現が偶数インデックスに現れます。

この性質を利用して、まず中央インデックスmidを求めます。midが偶数の場合はA[mid]とA[mid+1]を比較し、両者が同じであれば一意の要素は右側に存在するため探索範囲を右へ移動し、異なれば左側へ移動します。midが奇数の場合はA[mid]とA[mid-1]を比較し、同じであれば右側へ、異なれば左側へ探索範囲を狭めていきます。この処理を繰り返すことで、O(log n)の時間計算量で一意の要素を特定できます。

実装例

#include<iostream>
using namespace std;
void findSingleElement(int *arr, int left, int right) {
   if (left > right)
      return;
   if (left==right) {
      cout << "The required element is: "<< arr[left];
      return;
   }
   int mid = (left + right) / 2;
   if (mid%2 == 0) {
      if (arr[mid] == arr[mid+1])
         findSingleElement(arr, mid+2, right);
      else
         findSingleElement(arr, left, mid);
   }else{
      if (arr[mid] == arr[mid-1])
         findSingleElement(arr, mid+1, right);
      else
         findSingleElement(arr, left, mid-1);
   }
}
int main() {
   int arr[] = {1, 1, 3, 3, 4, 4, 5, 6, 6, 7, 7, 9, 9};
   int len = sizeof(arr)/sizeof(arr[0]);
   findSingleElement(arr, 0, len-1);
}

出力

The required element is: 5

計算量の分析

このアルゴリズムの時間計算量はO(log n)です。各ステップで探索範囲が半分に縮小されるため、線形走査によるO(n)のアプローチと比較して大幅に効率的です。空間計算量については、再帰呼び出しのスタックを除けばO(1)となります。なお、再帰をループに書き換えることで、空間計算量をO(1)に抑えることも可能です。