C++の0と1の無限にソートされた配列で最初の1のインデックスを見つけます

この問題では、ブール値（0と1のみ）で構成される無限配列bin[]がソートされた順序で与えられます。私たちのタスクは、0と1の無限にソートされた配列から最初の1のインデックスを見つけることです 。

ここに、配列に1が存在することを保証する無限配列があります。

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

Input : bin[] = {0, 0, 0, 1, 1, ....}
Output : 3

説明 −

First 1 of the binary array is encountered at index 3.

ソリューションアプローチ

この問題を解決するには、基本的に配列内の最初の1のインデックスを見つける必要があります。そのために、検索手法を使用できます。

1つのアプローチは、線形探索を使用することです。無限ループを使用して配列をトラバースします。そして、配列の最初の1のインデックスを返します。それ以外の場合は、-1を出力します。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
double find1stOneInfiniteArray(int bin[]) {
   int i = 0;
   while(1){
      if (bin[i] == 1)
         return i;
      i++;
   }
   return -1;
}
int main() {
   int bin[] = { 0, 0, 0, 1, 1, 1 };
   cout<<"The index of 1st occurrence of 1 in infinite array is "<<find1stOneInfiniteArray(bin);
   return 0;
}

出力

The index of 1st occurrence of 1 in infinite array is 3

別の検索手法 使用できるのは、配列がソートされるときの二分探索です。

上限がないため、アルゴリズムを更新する必要があります。インデックス値1から始まるhighの値を、最初の1の発生インデックスに2倍にすることで見つけます。

これらの境界を使用して、二分探索を使用してインデックスを見つけることができます。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
double find1stOneInfiniteArray(int bin[], int low, int high) {
   int mid;
   while (low <= high) {
      mid = (low + high) / 2;
      if (bin[mid] == 1 && (mid == 0 || bin[mid - 1] == 0))
         return mid;
      else if (bin[mid] == 1)
         high = mid - 1;
      else
         low = mid + 1;
   }
   return -1;
}
int main() {
   int bin[] = { 0, 0, 0, 1, 1, 1, 1 };
   int low = 0;
   int high = 1;
   while(bin[high] != 1){
      low = high;
      high *= 2;
   }
   cout<<"The index of 1st occurrence of 1 in infinite array is " <<find1stOneInfiniteArray(bin,low, high);
   return 0;
}

出力

The index of 1st occurrence of 1 in infinite array is 3