Binary Search Solution for Max Number of Surpassers

Question

For an array of integers, the superior integer element is the element on the right side that is larger than it.

For example, {10,3,4,5,2} , surpass 3 - 4 and 5 , and 10 has no surpass.

So the problem is Max Number of Surpassers

For an array of integers

Print the maximum number of dips

In principle, we need to get the number of transmissions of each element and, finally, to deduce their maximum.

For instance,

The maximum number of opponents for {10,3,4,5,2} is 2, since 3 has 2 to beat.

---

I am wondering if there is an O(nLogn) that uses binary search.

I had this question because chapter 2 in Pearls of Functional Algorithm Design says:

In this pearl, we solve a small programming exercise by Martin Rem (1988a). While the Rems solution uses binary search , our solution is another application of separation and conquest.

Although I got a functional solution, I cannot imagine a binary search for arrays.

Any ideas?

Answer 1

Solution 1

I don't know if this matches the Rem solution, but you can easily solve it with a binary search tree.

Initialize an empty binary search tree, and then iterate in reverse order through the array.

Paste each item into the binary search tree, and then count all the items in the tree above the item value. (If in each subtree the number of elements contained in it is stored, then these operations can be performed in O (logn) if the corresponding balanced tree is used.)

The maximum number of successors is determined by the largest observed counter.

Decision 2

A potentially faster solution with a similar basic idea is to use aka a Fenwick tree to store items. This data structure can be accessed to get the number of elements above a given value, so they can be used in the same way as the binary search tree in solution 1.

This will have the same O (nlogn) complexity as solution 1, but can be faster in practice, since it has less memory.

Answer 2

Here is one solution that uses binary search, but I don’t think it is what you are looking for (binary search is not the main method used in the algorithm). Most of the work for this solution is done by a combination of sorting and the Fenwick tree. The binary search component is likely to be replaced by a hash map or binary search tree.

Anyway, here is the code. Let me know if you have any questions:

 import java.util.Arrays; public class MaxSurpassersFenwick { public static void main(String[] args) { // The number of surpassers for a value is the number of values to the right and bigger. // The number of surpassers for { 2, 7, 5, 5, 2, 7, 0, 8, 1 } are { 5, 1, 2, 2, 2, 1, 2, 0, 0 }. // The max number of surpassers is thus 5. // The code I have written runs in O(n lg n) time. int[] values = new int[] { 2, 7, 5, 5, 2, 7, 0, 8, 1 }; System.out.println("The max number of surpassers for any value in " + Arrays.toString(values) + " is " + getMaxNumSurpassers(values) + "."); } public static int getMaxNumSurpassers(int[] values) { if (values == null) { throw new IllegalArgumentException("Array of values cannot be null!"); } int n = values.length; if (n <= 1) { return 0; } int[] numSurpassers = getNumSurpassers(values); int maxNumSurpassers = numSurpassers[0]; for (int i = 1; i < n; ++i) { maxNumSurpassers = Math.max(maxNumSurpassers, numSurpassers[i]); } return maxNumSurpassers; } public static int[] getNumSurpassers(int[] values) { if (values == null) { throw new IllegalArgumentException("Array of values cannot be null!"); } int n = values.length; int[] sortedValues = values.clone(); FenwickTree numValues = new FenwickTree(n); int[] numSurpassers = new int[n]; Arrays.sort(sortedValues); // Iterate through the values from right to left for (int i = n - 1; i >= 0; --i) { // Find the index of the current value in the sorted array of values // If the value occurs more than once, return the last index for that value int lastOccurrenceIndex = binarySearchLastOccurrence(sortedValues, values[i]); // Count the number of values we've seen that are greater than the current value numSurpassers[i] = numValues.sum(lastOccurrenceIndex + 1, n - 1); // Mark the current value as seen numValues.add(lastOccurrenceIndex, 1); } return numSurpassers; } private static int binarySearchLastOccurrence(int[] values, int valueToFind) { int low = 0; int high = values.length - 1; while (low <= high) { int mid = low + (high - low) / 2; if (mid == high || (values[mid] == valueToFind && values[mid] < values[mid + 1])) { return mid; } else if (values[mid] > valueToFind) { high = mid - 1; } else { low = mid + 1; } } return -1; } private static class FenwickTree { private int size; private int[] values; public FenwickTree(int size) { this.size = size; this.values = new int[size]; } public void add(int index, int value) { while (index < this.size) { this.values[index] += value; index |= index + 1; } } public int prefixSum(int index) { int sum = 0; int n = index + 1; while (n > 0) { sum += this.values[n - 1]; n &= n - 1; } return sum; } public int sum(int leftIndex, int rightIndex) { if (leftIndex > rightIndex) { return 0; } int rightSum = this.prefixSum(rightIndex); int leftSum = (leftIndex > 0) ? this.prefixSum(leftIndex - 1) : 0; return (rightSum - leftSum); } } }