Find the index of first 1 in an infinite sorted array of 0s and 1s

Problem statement:

You are given a sorted array of infinite length of 0’s and 1’s. You need to find the first occurrence of 1.

Example:

array = {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1}

Output:

1 is found at the index 10.

Solution:

We can apply binary search.

But to apply binary search, we know the start index i.e 0. But we also need to get the end index.

As the array is infinite, how will you find the end index?

Let us understand how we get the end index with the help of an example:

Suppose you have the infinite array {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1} and you need to find the first 1.

Initially we assign index 0 as start index and index 1 as end index.

Then we check, if the value at end index is 1.

if it is, then we got the end index, and we do the binary search for key element as 1.

Else we double the end index and check if the element at the end index is equal to 1.

If it is equal to 1, then there might be chances that the previous elements can also be 1. Hence we perform binary search with the updated start and end index.

When we are searching for the key element, there is a chance that arr[mid] == 1. But that might not be the first occurrence. Hence we need to additionally check if the element besides it is 0. If the element besides to it is 0, then it means that the mid index is the first occurrence of the element 1.

Solution in C++

#include <iostream>
using namespace std;

int binary_search(int arr[], int start, int end, int key) 
{ 
    while (start <= end) 
    { 
        int mid = start + (end - start) / 2; 
  
          if (arr[mid] == key && (mid == 0 || arr[mid - 1] == 0)) 
            return mid; 
  
          if (arr[mid] < key) 
            start = mid + 1; 
  
          else
            end = mid - 1; 
    } 
  
    return -1; 
} 

int get_end_index(int arr[]) 
{ 
    int start = 0;
    int end = 1; 
  
    while (arr[end] == 0) 
    { 
        start = end; // store previous end index 
        end = 2*end; // double end index
    } 
    
    // now we got start and end index, perform normal binary search
    return binary_search(arr, start, end, 1); 
} 


int main(void) 
{ 
    int arr[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1}; 

    int result = get_end_index(arr);

    cout<<" The first 1 is found at index " <<result<<endl;

    return 0; 
} 

Output:

The first 1 is found at index 9