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

Issue

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.

Solution

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

Answered By - Anderson