Skip to main content
Code Review

Return to Answer

replaced http://codereview.stackexchange.com/ with https://codereview.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

Building upon @Barry@Barry's answer, Java already has Arrays.binarySearch(int[], int, int, int) that can perform the binary search without having to write additional code ourselves. :)

Building upon @Barry's answer, Java already has Arrays.binarySearch(int[], int, int, int) that can perform the binary search without having to write additional code ourselves. :)

Building upon @Barry's answer, Java already has Arrays.binarySearch(int[], int, int, int) that can perform the binary search without having to write additional code ourselves. :)

added 1806 characters in body
Source Link
h.j.k.
h.j.k.
  • 19.2k
  • 3
  • 36
  • 93

Visualizing the steps taken can be done with a slight modification to STEPPER:

private static final BiFunction<int[], Integer, Integer> STEPPER = (sorted, i) -> {
        int r = Arrays.binarySearch(sorted, i, sorted.length, sorted[i] + 1);
        r = r < 0 ? Math.abs(r + 1) : r;
        System.out.printf("DEBUG: current (index = %d, value = %d); "
                            + "next (index = %d, value = %s)%n",
                            i, sorted[i], r, 
                            r >= sorted.length ? "END" : sorted[r]);
        return r;
    };

Given this example:

countUnique(new int[]{0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 5, 5, 5, 5, 5});

// Output
DEBUG: current (index = 0, value = 0); next (index = 4, value = 1)
DEBUG: current (index = 4, value = 1); next (index = 7, value = 2)
DEBUG: current (index = 7, value = 2); next (index = 11, value = 4)
DEBUG: current (index = 11, value = 4); next (index = 14, value = 5)
DEBUG: current (index = 14, value = 5); next (index = 19, value = END)
Input(19): [0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 5, 5, 5, 5, 5]

The answer is the number of DEBUG lines printed, i.e. 5. It works by jumping across any indices of the numbers 0 -> 1 -> 2 -> 4 -> 5. The any index part is a known effect from the method's Javadoc:

If the range contains multiple elements with the specified value, there is no guarantee which one will be found.

This still suffices for our usage here as we only need to hit any of the next larger number. Also, since 3 is not present in the list, 4 is returned after 2, and this is where the check for r < 0 is required to convert the result of Arrays.binarySearch() to a positive, usable index.

Visualizing the steps taken can be done with a slight modification to STEPPER:

private static final BiFunction<int[], Integer, Integer> STEPPER = (sorted, i) -> {
        int r = Arrays.binarySearch(sorted, i, sorted.length, sorted[i] + 1);
        r = r < 0 ? Math.abs(r + 1) : r;
        System.out.printf("DEBUG: current (index = %d, value = %d); "
                            + "next (index = %d, value = %s)%n",
                            i, sorted[i], r, 
                            r >= sorted.length ? "END" : sorted[r]);
        return r;
    };

Given this example:

countUnique(new int[]{0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 5, 5, 5, 5, 5});

// Output
DEBUG: current (index = 0, value = 0); next (index = 4, value = 1)
DEBUG: current (index = 4, value = 1); next (index = 7, value = 2)
DEBUG: current (index = 7, value = 2); next (index = 11, value = 4)
DEBUG: current (index = 11, value = 4); next (index = 14, value = 5)
DEBUG: current (index = 14, value = 5); next (index = 19, value = END)
Input(19): [0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 5, 5, 5, 5, 5]

The answer is the number of DEBUG lines printed, i.e. 5. It works by jumping across any indices of the numbers 0 -> 1 -> 2 -> 4 -> 5. The any index part is a known effect from the method's Javadoc:

If the range contains multiple elements with the specified value, there is no guarantee which one will be found.

This still suffices for our usage here as we only need to hit any of the next larger number. Also, since 3 is not present in the list, 4 is returned after 2, and this is where the check for r < 0 is required to convert the result of Arrays.binarySearch() to a positive, usable index.

Source Link
h.j.k.
h.j.k.
  • 19.2k
  • 3
  • 36
  • 93

Building upon @Barry's answer, Java already has Arrays.binarySearch(int[], int, int, int) that can perform the binary search without having to write additional code ourselves. :)

Using a very similar approach of modeling the next index \$m\$ as where the next larger value (\$V\$) of the current value (\$arr[n]\$) should be inserted, we have the following BiFunction<int[], Integer, Integer> implementation:

private static final BiFunction<int[], Integer, Integer> STEPPER = (sorted, i) -> {
        int r = Arrays.binarySearch(sorted, i, sorted.length, sorted[i] + 1);
        return r < 0 ? Math.abs(r + 1) : r;
    };

We need to handle for r < 0 as \$V\$ may not exist in the array, in which case Arrays.binarySearch() will return (-(insertion point) - 1). For pre-Java 8, this can easily be converted into a method as well.

The full method can then be:

private static int countUnique(int[] sortedArray) {
    if (sortedArray.length == 0) {
        return 0;
    }
    int counter = 1;
    for (int i = STEPPER.apply(sortedArray, 0); i < sortedArray.length;
                i = STEPPER.apply(sortedArray, i)) {
        counter++;
    }
    return counter;
}

After taking care of handling an empty array, we initialize counter as 1 (for the first element) and i to be the index of the next larger value than the first element. After each loop, i is then assigned the index of the next larger value than the current iteration's element.