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]을 비교하고 둘 다 같으면 필요에 따라 왼쪽이나 오른쪽으로 이동합니다. 그렇지 않으면 mid가 홀수일 때 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