0

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.

tootiefairy
  • 21
  • 3
  • 2
    With binary search you can find the index to the value 80, and then the index is the number of the elements less than 80 (assuming ascending order). – gthanop Jan 08 '21 at 12:49
  • 2
    or, stream, filter, ... – Stultuske Jan 08 '21 at 12:50
  • 1
    "I was thinking Binary Search but then again i'm not searching for any key" - well you are, in that you're trying to find *where that key lives in the array* (or where it would be if it did exist). – Jon Skeet Jan 08 '21 at 12:58

2 Answers2

5

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

Anderson
  • 169
  • 5
  • 2
    I know that we were probably writing the answer at the same time, but please make sure all special cases are handled properly. 1+ for giving example code. – gthanop Jan 08 '21 at 13:07
  • 1
    thanks for the point @gthanop ! I added some considerations at the end of the answer to consider the case of duplicates. – Anderson Jan 08 '21 at 13:30
  • 3
    No problem. Also, welcome to SO. To be honest, I couldn't think of the solution you provided in the edit. Nice job done. This should be the answer now (because it is more complete). – gthanop Jan 08 '21 at 13:34
  • Why count(70) returns 4? is 70 counted too? – Alessandro Parisi May 26 '22 at 19:49
  • You are absolutely right @AlessandroParisi, I reviewed and edited the response accordingly. – Anderson May 27 '22 at 07:15
0

Since Java 9 you can use takeWhile and dropWhile methods if the source array is ordered:

int key = 80, arr[] = {21, 32, 58, 70, 100, 4342};

System.out.println("Count: " + Arrays.stream(arr)
        .takeWhile(i -> i < key)
        .peek(i -> System.out.print(i + " "))
        .count()); // 21 32 58 70 Count: 4

System.out.println("Count: " + Arrays.stream(arr)
        .dropWhile(i -> i < key)
        .peek(i -> System.out.print(i + " "))
        .count()); // 100 4342 Count: 2