0と1のソートされた配列が与えられた場合、C++で配列の遷移点を見つけます

0と1のみを含むソートされた数値の配列が与えられた場合、遷移点を見つけます。遷移点は、配列に最初に現れる「1」のインデックスです。たとえば、

入力-1 −

N = 6
arr[ ] = {0,0,0,0,1,1}

出力 −

4

説明 − 0と1を含む特定の配列では、インデックス「4」の要素の番号が「1」であることがわかります。

入力-2 −

N = 5
arr[ ] = {0,0,1,1,1}

出力 −

2

説明 − 0と1を含む指定された配列では、インデックス「2」の要素の番号が「1」であることがわかります。したがって、2を返します。

この問題を解決するためのアプローチ

与えられた整数の配列で、最初の1のインデックスを見つける必要があります。この特定の問題を解決するには、二分探索法を使用して最初の「1」のインデックスを見つけることができます。

• N個の2進数の配列を入力してください

• これで、関数transitionPoint（int * arr、int n）は配列を入力とそのサイズとして受け取り、配列に最初に現れる「1」のインデックスを返します。

• 「0」と「1」として初期化される2つのポインタを低く、高くします。

• 次に、配列の中点を見つけて、それが「1」であるかどうかを確認します。

• 配列の中央が「1」の場合はインデックスを返し、そうでない場合は先に進んで確認します。

• ローポインタをインクリメントして、もう一度「1」を確認します。

• 「1」が表示されなくなるまで手順を繰り返します。

例

#include <bits/stdc++.h>
using namespace std;
int transitionPoint(int *arr, int n){
   int low=0;
   int high= n-1;
   while(low<=high){
      int mid = (low+high)/2;
      if(arr[mid]==0)
         low= mid+1;
      else if(arr[mid]==1){
         if(mid==0 || (mid>0 && arr[mid-1]==0))
            return mid;
         high= mid-1;
      }
   }
   return -1;
}
int main(){
   int n= 6;
   int arr[n]= {0,0,0,1,1,1};
   int ans= transitionPoint(arr,n);
   if(ans>=0){
      cout<<"Transition Point is:"<<ans<<endl;
   }
   else{
      cout<<"Not Found"<<endl;
   }
   return 0;
}

出力

上記のコードを実行すると、次のように出力が生成されます

Transition Point is: 3

指定された配列{0,0,0,1,1,1}には、インデックス「3」に要素「1」が存在するため、出力は「3」として取得されます。