C++를 사용하여 정렬된 배열에서 유일하게 누락된 숫자 찾기

이 문제에서 배열에 하나의 값이 누락된 1에서 N까지의 값을 포함하는 크기 N의 arr[]이 제공됩니다. 우리의 임무는 정렬된 배열에서 유일하게 누락된 숫자를 찾는 것입니다. .

문제를 이해하기 위해 예를 들어보겠습니다.

입력

arr[] = {1, 2, 3, 5, 6, 7}

출력

4

솔루션 접근 방식

문제에 대한 간단한 해결책은 정렬된 배열을 선형으로 순회하는 것입니다. 그런 다음 arr[i] =(i + 1)이라는 사실을 사용하여 누락된 값을 확인합니다.

예시 1

솔루션 작동을 설명하는 프로그램

#include <iostream>
using namespace std;
int findMissingValArray(int arr[], int N){
   for(int i = 0; i < N; i++){
      if(arr[i] != (i+1))
         return (i+1);
   }
   return -1;
}
int main(){
   int arr[] = {1, 2, 3, 4, 6};
   int N = sizeof(arr)/sizeof(arr[0]);
   cout<<"The missing value from the array is "<<findMissingValArray(arr, N);
   return 0;
}

출력

The missing value from the array is 5

문제를 해결하는 또 다른 방법은 이진 검색을 사용하고 중간 값을 확인하는 것입니다. mid의 값이 mid+1이고 (mid - 1)의 값이 (mid)이면 왼쪽 하위 배열을 탐색하고 그 반대의 경우도 마찬가지입니다.

예시 2

솔루션 작동을 설명하는 프로그램

#include <iostream>
using namespace std;
int findMissingValArray(int arr[], int N){
   int s = 0, e = N - 1;
   while (s <= e) {
      int mid = (s + e) / 2;
      if (arr[mid] != mid + 1 && arr[mid - 1] == mid)
         return (mid + 1);
      if (arr[mid] != (mid + 1))
         e = (mid - 1);
      else
         s = (mid + 1);
   }
   return -1;
}
int main(){
   int arr[] = {1, 2, 3, 4, 6};
   int N = sizeof(arr)/sizeof(arr[0]);
   cout<<"The missing value from the array is "<<findMissingValArray(arr, N);
   return 0;
}

출력

The missing value from the array is 5