### PROBLEM LINK:

**Author:** Suraj Prakash

**Tester:** Aditya Kumar

**Editorialist:** Suraj Prakash

### DIFFICULTY:

Easy

### PREREQUISITES:

Ad-hoc, Binary Search

### PROBLEM

Compute the count of elements (floating point decimals) greater than **K**, if the list of non repeating elements was sorted.

### EXPLANATION

To find the number of elements greater than **K**, what we can do is to simply iterate through the array and count the number of elements greater than **K**, this is an approach which will run in time for smaller constraints. This will lead to a complexity of \mathcal{O}(N * Q)

For better efficiency this can be done using binary search in \mathcal{O}(\log (N) * Q), since we need to count the number of elements greater than **K**.

```
int find(vector<double> &v, int l, int h, double f){
int low = l, high = h, mid;
while (low < = high){
mid = (low + high) >> 1;
if (v[mid] == f)
return (h - mid);
else if (v[mid] > f)
high = mid - 1;
else
low = mid + 1;
}
return h - low + 1;
}
```

*STL offers inbuilt binary search which can be used to solve this problem using a line of code.*

**N - (upper_bound(arr, arr + N, K) - arr)**

### OPTIMAL COMPLEXITY:

\mathcal{O}(Q*\log(N))

### AUTHOR’S SOLUTION:

Author’s solution can be found here.

Tester’s solution will be uploaded soon.