Find the number of elements greater than k in a sorted array using C++

In this problem, we are given an array arr[] consisting of N sorted integer values and an integer k. Our task is to Find the number of elements greater than k in a sorted array.

Example

Here are some examples of counting the array elements greater than the given target element:

Input:
arr = {6, 12, 16, 23, 32, 45, 48, 50}
target = 20
Output: 5

Input:
arr = {6, 12, 15, 20, 32, 45, 48, 50}
target = 20
Output: 4

Finding number of elements greater than k in a sorted array

Here is a list of approaches for counting the number of elements greater than the target element in the sorted array:

• Using Linear Search
• Using Binary Search
• Using upper_bound() Function

Using Linear Search

To count the number of elements greater than the given target elements in a sorted array, we have used the linear search algorithm. In linear search, we traverse each element and compare it with the key element to be found.

• Here, we traverse each array element to compare it with the given target element.
• For each element greater than the target element, we increase the counter by 1.
• After the completion of the for loop, we return the total count.

Example

The example given below uses the linear search for counting the number greater than the given target:

#include <iostream>
using namespace std;
int countGreater(int arr[], int n, int target)
{
   int count = 0;
   for (int i = 0; i < n; i++)
   {
      if (arr[i] > target)
         count++;
   }
   return count;
}
int main()
{
   int arr[] = {10, 25, 43, 49, 55, 63, 87};
   int n = sizeof(arr) / sizeof(arr[0]);
   int target = 45;
   cout << "Given array is: ";
   for (int i = 0; i < n; i++)
   {
      cout << arr[i] << " ";
   }
   cout << "\nNumber of elements greater than " << target
        << " is: " << countGreater(arr, n, target) << endl;
   return 0;
}

The output of the above code is as follows:

Given array is: 10 25 43 49 55 63 87 
Number of elements greater than 45 is: 4

Using Binary Search

In this approach, we have used the binary search approach for counting the elements greater than the target element. In the binary search, we compare the middle element with the target element. Based on the comparison with the middle element, we then search in the left or right half of the array.

• We have defined two pointer variables low and high that initially point to the starting and last index of the array.
• Then, we calculate the middle element of the array and compare the target with the middle element.
• If the middle element is greater than the target element then we store the middle index in the counter variable and decrease the high pointer by 1.
• If the middle element is not greater than the target element, then we increase the low pointer by 1.
• We repeat the above three steps until the low pointer reaches the high pointer and return the count.

Example

The following example uses the above steps for implementing binary search for counting elements greater than the target element:

#include <iostream>
using namespace std;
int countGreater(int arr[], int n, int target)
{
   int low = 0, high = n - 1, count = -1;
   while (low <= high)
   {
      int mid = low + (high - low) / 2;
      if (arr[mid] > target)
      {
         count = mid;
         high = mid - 1;
      }
      else
      {
         low = mid + 1;
      }
   }
   return count == -1 ? 0 : n - count;
}
int main()
{
   int arr[] = {10, 25, 43, 49, 55, 63, 87};
   int n = sizeof(arr) / sizeof(arr[0]);
   int target = 45;
   cout << "Given array is: ";
   for (int i = 0; i < n; i++)
   {
      cout << arr[i] << " ";
   }
   cout << "\nNumber of elements greater than " << target
        << " is: " << countGreater(arr, n, target) << endl;
   return 0;
}

The output of the above code is as follows:

Given array is: 10 25 43 49 55 63 87 
Number of elements greater than 45 is: 4

Using upper_bound() Function

The upper_bound() function returns a pointer pointing to the first element in the sorted range that is greater than the given value.

• Here, using the upper_bound() function, we get the address of the first element greater than the target element.
• Then, by subtracting this index from the starting index, we get the count of the elements smaller than the target element.
• Then we subtract the count value obtained in the previous step from total array length n to get the count of elements greater than the target element.

Example

In this example, we have used the upper_bound() function to count the elements greater than the target element.

#include <iostream>
#include <algorithm>
using namespace std;
int countGreater(int arr[], int n, int target)
{
   int count = n - (upper_bound(arr, arr + n, target) - arr);
   return count;
}
int main()
{
   int arr[] = {10, 25, 43, 49, 55, 63, 87};
   int n = sizeof(arr) / sizeof(arr[0]);
   int target = 45;
   cout << "Given array is: ";
   for (int i = 0; i < n; i++)
   {
      cout << arr[i] << " ";
   }
   cout << "\nNumber of elements greater than " << target
        << " is: " << countGreater(arr, n, target) << endl;
   return 0;
}

The output of the above code is as follows:

Given array is: 10 25 43 49 55 63 87 
Number of elements greater than 45 is: 4

Complexity Comparison

Here is a comparison of the time and space complexity of all the above approaches.