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

In this problem, we are given an 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 a sorted array of 0's and 1's.

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 from index 0 to the end of array. 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 find1stOneInArray(int bin[], int n) {
   for (int i = 0; i < n; i++)
      if (bin[i] == 1)
         return i;
      return -1;
}
int main() {
   int bin[] = { 0, 0, 0, 1, 1, 1 };
   int n = sizeof(bin) / sizeof(bin[0]);
      cout<<"The index of 1st occurrence of 1 in array is "<<find1stOneInArray(bin,n);
      return 0;
}

Output

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

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

Example

Program to illustrate the working of our solution

#include <iostream>
using namespace std;
double find1stOneInArray(int bin[], int n) {
   int low = 0;
   int high = (n - 1);
   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 n = sizeof(bin) / sizeof(bin[0]);
      cout<<"The index of 1st occurrence of 1 in array is "<<find1stOneInArray(bin,n);
   return 0;
}

Output

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