Using binary search to count number of elements smaller/larger than a given number

Question

Given a number current, find the number of values in an array which are larger and smaller than that value.

//sort array for binary search
 int[] digits = Arrays.stream(sc.nextLine()
            .split(" "))
            .mapToInt(Integer::parseInt)
            .sorted()
            .toArray();

//for duplicate values, find higher index of current.

   while(low <= high){
        int mid = low + (high - low)/2;
        if(digits[mid] > current){
            high = mid - 1;
        }else if (digits[mid] == current){
            startindex = mid;
            high = mid - 1;   
        }else{
            startindex = mid;
            low = mid +1;
        }
    }

//for duplicate values, find lower index of current.
    int endindex = -1;
    low = 0;
    high = no_digits - 1;

    while(low <= high){
        int mid = low + (high - low)/2;
        if(digits[mid] > current){
            high = mid - 1;
        }else if (digits[mid] == current){
            endindex = mid;
            low = mid + 1;   
        }else{
            endindex = mid;
            low = mid + 1;
        }
    }

    System.out.println(endindex + "-" + startindex);

    if(digits[0] > current){
        smallest = 0;
        largest = no_digits;
        System.out.println(String.format("Smaller: %d, Greater: %d", smallest, largest));
    } else if (digits[no_digits - 1] < current){
        smallest = no_digits;
        largest = 0;
        System.out.println(String.format("Smaller: %d, Greater: %d", smallest, largest));
    }else {
        smallest = startindex;
        largest = no_digits - endindex - 1;                
        System.out.println(String.format("Smaller: %d, Greater: %d", smallest, largest));
    }
}

}

Sample input:

5 8 7 2 4 3 7 9 1 9 - Array of ints.

7
0
100
3
6

Output:

Smaller: 5, Greater: 3
Smaller: 0, Greater: 10
Smaller: 10, Greater: 0
Smaller: 2, Greater: 7
Smaller: 5, Greater: 5

My results:

6-5 //start and end index.
Smaller: 5, Greater: 3
-1--1 
Smaller: 0, Greater: 10
9-9
Smaller: 10, Greater: 0
2-2
Smaller: 2, Greater: 7
4-4
Smaller: 5, Greater: 4

I managed to come out with the above algorithm which accounts for values larger or lower than any value in the array.

However, I am unable to find a solution to account for values that are nonexistent in the array without iterating though the array since I need to accomplish the above in O((N+Q) log N) time.

In this case, this would be the last test case where the value is 6. 6 does not exist in the array but I will still need to count all values higher/lower than 6.

Answer 1

Binary search algorithm produces the "insertion point" for values that do not exist in the array. Your startIndex and endIndex would give you the first "eligible" item, or the one right next to it. In other words, if you are looking for all values less than 6, the search for endpoint would yield the index of 5.

Note that you don't need to roll your own binary search algorithm: Java provides an implementation for you.

Reference: Arrays.binarySearch

Answer 2

EDIT The question has been edited, now it contains an additional requirement that the algorithm should work fast for multiple queries, more precisely: the overall runtime should be O((N + Q) * log(N)) where N is the size of the array and Q is the number of queries.

The approach below works only for Q = 1.

---

I don't see any reason not to do it in linear O(N) time.

// get this from scanner
int number = 5;
int[] array = {6, 2, 7, 4, 1, 42};

// the "algorithm"
int numLessThan = 0;
int numGreaterThan = 0;
for (int i: array) {
  if (i < number) numLessThan++;
  if (i > number) numGreaterThan++;
}
System.out.println(
  "Num greater than: " + numGreaterThan + " " +
  "Num less than: " + numLessThan
);

Output:

Num greater than: 3 Num less than: 3

If you insist on doing it with streams:

long numLessThan = Arrays.stream(array).filter(x -> x < number).count();
long numGreaterThan = Arrays.stream(array).filter(x -> x > number).count();

Even though it traverses the array twice, it is still O(N).

Answer 3

Since you use a Stream anyway, with a map-call no less, you're iterating the whole array anyway.

So just do

class Counters {
    AtomicInteger smaller = new AtomicInteger(0);
    AtomicInteger larger = new AtomicInteger(0);
    private final int upperLimit;
    private final int lowerLimit;
    public Counters(int up, int down) {
        upperLimit = up;
        lowerLimit = down;
    }
    public void consider(int value) {
        if (value > upperLimit) larger.incrementAndGet();
        if (value < lowerLimit) smaller.incrementAndGet();
    }
    public int getSmaller() { return smaller.get(); }
    public int getLarger() { return larger.get(); }
}

Counters c = new Counters(upper, lower);
IntStream.of(yourValues).parallel().forEach(c::consider);
// your output here
System.out.printf("Smaller: %d - Larger: %d", c.getSmaller(), c.getLarger());

or a more generic version

class MatchCounter<T> {
    AtomicInteger count = new AtomicInteger(0);
    private final Predicate<T> match;
    public MatchCounter(Predicate<T> m) { match = m; }
    public void consider(T value) {
        if (m.test(value)) { count.incrementAndGet(); }
    }
    public int getCount() { return count.get(); }
}

MatchCounter<Integer> smaller = new MatchCounter<>(i -> i < lower);
MatchCounter<Integer> larger = new MatchCounter<>(i -> i > upper);
Consumer<Integer> exec = smaller::consider;
Stream.of(yourArray).parallel().forEach(exec.andThen(larger::consider));
System.out.printf("Smaller: %d - Larger: %d", smaller.getCount(), larger.getCount());

Answer 4

See Arrays which would come handy here.

void stats(int[] a, int sought) {
    a = Arrays.copyOf(a, a.length);
    Arrays.sort(a);
    int index = Arrays.binarySearch(a, sought);
    int smaller, larger;
    if (index < 0) {
        // Not found.
        index = ~index; // Insertion position.
        smaller = index;
        larger = index:
    } else {
        // Found.
        smaller = index;
        while (smaller > 0 && a[smaller] == sought) {
            --smaller;
        }
        while (index <= 0 && a[index] == sought) {
            ++index;
        }
    }
    larger = a.length - index;
    int equals = index - smaller;
    System.out.printf("Smaller %d, equal %d, larger %d.%n",
            smaller, equals, larger); 
}

As you see, when finding an element, it would suffice to loop back O(N) which is less than sorting O(N log N).

Faster - O(log N) instead of O(N) for that part - would be if one could do a binary search on sought - 0.5 and sought + 0.5.

void stats(int[] a, int sought) {
    a = Arrays.copyOf(a, a.length);
    for (int i = 0; i < a.length; ++i) {
        a[i] *= 2;
    }
    Arrays.sort(a);
    int smallerI = Arrays.binarySearch(a, 2 * sought - 1);
    int largerI = Arrays.binarySearch(a, 2 * sought + 1);
    int smaller = ~smallerI;
    int larger = a.length - ~largerI;
    int equals = ~largerI - ~smallerI;
    System.out.printf("Smaller %d, equal %d, larger %d.%n",
            smaller, equals, larger); 
}

This uses doubled integers, which has the drawback that the valid domain of array values is halved.

In your case your own binary search algorithm should opt for this latter case (without doubling), using an implicit sought + 0.5, never finding, looking for an insertion position.

Answer 5

Okay, so after your edit you state you want to run several queries over the same array so preparation time is less important.

To do that, build a red-black tree from the array; that will give you a sorted structure that allows a search in O(log N).

So what you do for the "smaller" count is go to the left until you find a node with a value equal or larger than the lower limit; count all left children of that. Analogue for the larger (go to the right, find equal or smaller, count to the right).

It won't matter if the item is not present in the array because you're looking for an "equal-or-larger" so if e.g. 6 is not present but you find a 5, you'll count from there - only you add 1 to the count.

Answer 6

You just have to filter and then count occurences. For example :

public static void main(String[] args) {
    int[] values = {5, 8, 7, 2, 4, 3, 7, 9, 1, 9};
    printCount(values, 7);
    printCount(values, 0);
    printCount(values, 100);
    printCount(values, 3);
    printCount(values, 6);

}
private static void printCount(int[] values, int value) {
    long smallerCount = Arrays.stream(values).filter(v -> v < value).count();
    long largerCount  = Arrays.stream(values).filter(v -> v > value).count();
    System.out.println(String.format("Smaller : %d, Larger: %d", smallerCount, largerCount));
}