在C ++中查找数组中的阶乘和

考虑我们有一个已排序的数组A。它具有所有元素出现两次，但一个元素仅出现一次的情况。我们必须找到那个元素。如果数组为[1、1、3、3、4、4、5、6、6、7、7、9、9]，则单个元素为5。

我们将使用二进制搜索方法来解决此问题。单个元素之前的所有元素均在索引0、2、4，…处首次出现，并且在索引1、3、5，…处第一次出现，但在单个元素之后，第一个数字的所有出现都在奇数索引处，并且第二个元素将位于偶数索引位置。

因此，首先找到中间索引mid，如果mid是偶数，则比较A [mid]和A [mid + 1]，如果两者相同，则根据需要移至左侧或右侧。否则，当中点为奇数时，则比较A [mid]和A [mid – 1]，如果它们相同，则根据需要移至左侧或右侧。

示例

#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