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.

## Advertisement

## Answer

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:

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.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)`

.