Searching: Count the number of 1s in a sorted binary array

Problem Statement:

You are given a binary array, in decreasing order.

You need to count the number of 1’s in it.

Example:

Input: arr[] = [1, 1, 1, 1, 0, 0, 0]
Output: 4

Solution 1: Brute force approach

We do linear search for this solution.

Time Complexity: O(n)
Space Complexity: O(1)

Solution 2: Binary Search

We use binary search to find the last occurrence of 1.

If mid element is 0, then move to left.

If the mid is 1, and next element is 0 or last element, return mid+1.

Else check right half

Time Complexity: O(n log n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits.h>
#include <math.h>

using namespace std;


int solution_1 (vector<int> &arr) 
{

    int count = 0;

    for (int num : arr) 
    {
        if (num == 1) count++;
        else break;
    }
    return count;
}

int solution_2 (vector<int> &arr)
{   
    int n = arr.size();
    int ans = 0;
    int low = 0, high = n - 1;
    
    while (low <= high) 
    { 
        int mid = (low + high) / 2;

        if (arr[mid] == 0)
            high = mid - 1;
            
        else if (mid == n - 1 || arr[mid + 1] != 1)
            return mid + 1;
            
        else
            low = mid + 1;
    }
    return 0;
}

int main()
{
    vector<int> arr = { 1, 1, 1, 1, 1, 0, 0 };
    cout << solution_1(arr)<<endl;
    cout << solution_2(arr)<<endl;
    return 0;
}

Output

5
5