1.

Given a sorted array of 0s and 1s. The goal is to discover the index of the sorted array’s first '1'. It's possible that the array is made up entirely of 0s or 1s. If there are no 1's in the array, display "-1."

Answer»

Example:
Input: 
arr = {0, 0, 0, 0, 1, 1, 1}
Output :
4

Input :
Arr = {0, 0, 0, 0}
Output :
-1 

Approach:

It is given that the array is SORTED. We use this property of the array and apply binary search to find the first occurrence of 1 in the given array. We start with the whole array as our search space and find the middle element. If we encounter 0 as the middle element, it implies that our answer lies to the right side of the middle element. If we encounter 1 as the middle element, our answer can EITHER be this index or the indices left to the CURRENT middle if there are more 1s preceding the current middle.

Code:

 #include <bits/stdc++.h>using namespace std; // function to find the first occurrence of 1 in the give sorted arrayint findIndex(int arr[], int low, int high){ while (low <= high) { int mid = low + (high - low) / 2; // we CHECK if the mid element is a 1 and the mid - 1 element is 0 if (arr[mid] == 1 && (mid == 0 || arr[mid - 1] == 0)) return mid; // our answer lies to the left of mid, we reduce our search space else if (arr[mid] == 1) high = mid - 1; // our answer lies to the right of mid, we reduce our search space else low = mid + 1; } // we return -1 since 1 is not present in the array return -1;} int main(){ int arr[] = { 0, 0, 0, 0, 1, 1, 1, 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << findIndex(arr, 0, n - 1); return 0;}

Output:

 4

Explanation : 

In the above code, we defined a function named ‘findIndex’ which finds the first occurrence of the first one in the sorted array. We reduce the search space by changing the values of low and high as per the current value of the middle element. If low exceeds high, we return -1 which INDICATES that no 1 is present in the array.


Discussion

No Comment Found

Related InterviewSolutions