Queries for counts of array elements with values in given range

Hello Everyone,

Given an unsorted array of size n, find no of elements between two elements i and j (both inclusive).
Examples:

Input : arr = [1 3 3 9 10 4]
i1 = 1, j1 = 4
i2 = 9, j2 = 12
Output : 4
2
The numbers are: 1 3 3 4 for first query
The numbers are: 9 10 for second query

A simple approach will be to run a for loop to check if each element is in the given range and maintain their count. Time complexity for running each query will be O(n).

// Simple C++ program to count number of elements

// with values in given range.

#include <bits/stdc++.h>

using namespace std;

// function to count elements within given range

int countInRange( int arr[], int n, int x, int y)

{

// initialize result

int count = 0;

for ( int i = 0; i < n; i++) {

// check if element is in range

if (arr[i] >= x && arr[i] <= y)

count++;

}

return count;

}

// driver function

int main()

{

int arr[] = { 1, 3, 4, 9, 10, 3 };

int n = sizeof (arr) / sizeof (arr[0]);

// Answer queries

int i = 1, j = 4;

cout << countInRange(arr, n, i, j) << endl;

i = 9, j = 12;

cout << countInRange(arr, n, i, j) << endl;

return 0;

}

Output:

4
2

An Efficient Approach will be to first sort the array and then using a modified binary search function find two indices, one of first element greater than or equal to lower bound of range and the other of the last element less than or equal to upperbound. Time for running each query will be O(logn) and for sorting the array once will be O(nlogn).

// Efficient C++ program to count number of elements

// with values in given range.

#include <bits/stdc++.h>

using namespace std;

// function to find first index >= x

int lowerIndex( int arr[], int n, int x)

{

int l = 0, h = n - 1;

while (l <= h) {

int mid = (l + h) / 2;

if (arr[mid] >= x)

h = mid - 1;

else

l = mid + 1;

}

return l;

}

// function to find last index <= y

int upperIndex( int arr[], int n, int y)

{

int l = 0, h = n - 1;

while (l <= h) {

int mid = (l + h) / 2;

if (arr[mid] <= y)

l = mid + 1;

else

h = mid - 1;

}

return h;

}

// function to count elements within given range

int countInRange( int arr[], int n, int x, int y)

{

// initialize result

int count = 0;

count = upperIndex(arr, n, y) - lowerIndex(arr, n, x) + 1;

return count;

}

// driver function

int main()

{

int arr[] = { 1, 4, 4, 9, 10, 3 };

int n = sizeof (arr) / sizeof (arr[0]);

// Preprocess array

sort(arr, arr + n);

// Answer queries

int i = 1, j = 4;

cout << countInRange(arr, n, i, j) << endl;

i = 9, j = 12;

cout << countInRange(arr, n, i, j) << endl;

return 0;

}

Output:

4
2