C ++を使用して、ソートされた配列で欠落している唯一の番号を検索します

この問題では、1からNまでの値を含むサイズNのarr []が与えられ、配列に1つの値がありません。私たちのタスクは、並べ替えられた配列で欠落している唯一の番号を見つけることです。 。

問題を理解するために例を見てみましょう

入力

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