C ++で重複しているソートされた配列で等しい（または中間の）ポイントを検索する

n個の要素を持つ1つのソートされた配列があるとします。配列がソートされます。小さい要素の数が大きい要素の数と同じである配列に要素が存在するかどうかを確認する必要があります。等しい点が配列に複数回出現する場合は、最初に出現したインデックスを返します。そのようなポイントが存在しない場合は、-1を返します。要素がA=[1、1、2、3、3、3、3、3]のようであるとすると、等しい点はインデックス2にあり、要素はA [2]=2です。要素が1で、1つだけ大きい要素、つまり3です。

すべての個別の要素を格納するために、1つの補助配列を作成します。個別の要素の数が偶数の場合、等しい点を見つけることができません。そうでない場合、中央の要素が中点になります。

例

#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