Find Index of First 1 in Infinite Sorted Array of 0s and 1s in C++

In this problem, we are given an infinite array bin[] consisting of boolean values (only 0's and 1's) in sorted order. Our task is to find the index of first 1 in an infinite sorted array of 0's and 1's.

Here, we have an infinite array which guarantees that there exists 1 in the array.

Let's take an example to understand the problem,

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

Explanation −

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

Solution Approach

To solve the problem, we basically need to find the index of 1st 1 in the array. For that we can use a searching technique.

One approach can be using linear search, we will traverse the array using an infinite loop. And return the index of first 1 in the array, otherwise print -1.

Example

Program to illustrate the working of our solution

#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;
}

Output

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

Another searching technique that can be used is binary search as the array is sorted.

Just we need to update the algorithm as there is no upper bound, we will find it by doubling the value of high starting from index value 1 to the index of occurrence of first 1.

Using these bounds, we can find the index using binary search.

Example

Program to illustrate the working of our solution

#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;
}

Output

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