# How do I efficiently count elements less than a certain value in a sorted array?

Say for example I have a sorted array:

```[21, 32, 58, 70, 100, 4342]
```

And a key value `80`

How do I efficiently count all values from 80 below without iterating through the whole array with an if condition? I was thinking Binary Search but then again i’m not searching for any key, I just need the fastest way return the count of values less than or equal to key value.

You can use `Arrays.binarySearch`. According to the documentation it returns the index of the search key, if it is contained in the array; otherwise, `(-(insertion point) - 1)`. Using your example:

```import java.util.Arrays;

class Main {
public static void main(String args[]) {
int[] arr = {21, 32, 58, 70, 100, 4342};

int res70 = Arrays.binarySearch(arr, 70);// returns 3
int res80 = Arrays.binarySearch(arr, 80);// returns -5
}
}
```

With that in mind, you can use that information to get an efficient count: if the result is positive, the count is `result`, if the result is negative, the count is `(-result)-1` or `-(result+1)` (depending on your preference):

```import java.util.Arrays;

class Main {
public static void main(String args[]) {
int[] arr = {21, 32, 58, 70, 100, 4342};

System.out.println("Count is:" + count(arr, 70));// returns 3
System.out.println("Count is:" + count(arr, 80));// returns 4
}

private static int count(int[] sortedArray, int n) {
int result = Arrays.binarySearch(sortedArray, n);
if (result > -1) {
return result;
}
return (-result) - 1;
}
}
```

For the case where duplicates are possible, and multiple 80s exist in the array, there are two possible solutions:

1. Do a linear search from the result of the binary search. This would make the worst-case `O(n)` though, while still being `O(lg n)` on average.

2. Manually implement (or find a library that has) a binary search to find the last element equal to a value (while preserving the consideration for the element not found as the Java library does). An example of finding the last element exists in this answer: Last index of multiple keys using binary-search? That would keep worst-case at `O(lg n)`.