Searching: Count number of occurrence in a sorted array

Problem Statement:

You are given a sorted array a[] and a target element.

You need to find the number of times the target element is element.

Example:

Input: arr[] = [1, 1, 2, 2, 2, 2, 2, 2, 3], target = 2
Output: 6

Solution 1: Linear Search

We use linear search, and increment the count accordingly.

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

Solution 2: Binary Search

We get the lower bound, meaning, the first index of the element.
We get the upper bound, meaning, the last index of the element.
Then we get the difference between 2 indices.

Time Complexity: O(logn)
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 target) 
{
    int res = 0;
    for (int i = 0; i < arr.size(); i++) 
    {
      
         if (arr[i] == target)
            res++;
    }
  
    return res;
}


int solution_2 ( vector<int> &arr,  int target) 
{
    
    int l = lower_bound(arr.begin(), arr.end(), target) - arr.begin();
    int r = upper_bound(arr.begin(), arr.end(), target) - arr.begin();
      
    return r - l;
}


int main() 
{
    vector<int> arr = {1, 2, 2, 2, 2, 2, 2, 3, 4, 7, 8, 8};
    int target = 2;
    cout<< solution_1(arr, target);
    cout<< endl<<solution_2(arr, target);
    return 0;
}

Output

6
6