Epilogue to a binary search to find the range of matching indexes

Question

I am trying to find out the best practice for writing a loop which does one check and at the same time has to increment a value so that the while loop will eventually fail. Performance is important that's why I thought of using the least amount of variables.

Use case

In a decently low level method I do a binarySearch(array, key) which guarantees to find a key value in a sorted array if the key can be found. However it does not guarantees to find the first or last key first. But since I need the range of indexes in which the key excists (for other code later on) I try to find the last and first element in the array that matches. With this code I am trying to let lastSucceedingIndex hold the last index which holds the key:

while (lastSucceedingIndex < tailIndex && (array[++lastSucceedingIndex] == key)) {
}
lastSucceedingIndex--;

There is one situation in which a bug exists, namely when the lastSucceedingIndex is equal to the tailIndex: the while loop will fail and the ++lastSucceedingIndex will not happen. The lastSucceedingIndex-- is there in the end to fix the ++lastSucceedingIndex when it's not equal to the key, but since this does not happen in the last case it will decrement lastSucceedingIndex incorrectly. I wrote this loop for performance and I take this little bug for granted, it happens so rarely that it will effect less than 0.001% of all cases. This way it seems like I only need one counter and one variable, the loop could be executed as much as 17000 times before it finds its lastSucceedingIndex and the array is very large with possibly up to a million entries.

Are there any alternatives for performance and readability?

I analysed my code by the build in code analysis of my IDE and I get the remark

while statement has empty body at line

Which seems to indicate that having a loop with no lines in them is considered a possible bug by the compiler or at least bad practice. Now my question is, is having an empty loop considered bad practice? I could move the lastSucceedingIndex to the body and make it bug-free but that would require one extra addition like so:

while (lastSucceedingIndex < tailIndex && array[lastSucceedingIndex + 1] == key) {
    lastSucceedingIndex++;
}

1 less bug for millions upon millions of extra assembly instructions seems a hard trade-off to make.

Answer 1

Goals

I think your priorities are misplaced. Generally, your aims should be

1. Pick a reasonable algorithm to accomplish your task.
2. Implement it correctly and clearly (these goals are interrelated).
3. Then, if performance is an issue, make it faster.

You seem to have jumped straight to step 3.

Efficiency

Efficiency enhancements fall into two broad classes: algorithmic improvements and micro-optimizations. You should only consider micro-optimizations after exhausting algorithmic improvements. Micro-optimizations may reduce the running time by a few percent. On the other hand, your choice of algorithm will determine whether your program is able to scale gracefully at all. For example, a linear search is O(n), but a binary search is O(log n), so clearly the binary search is preferable.

If your binary search requires an epilogue to find the first and last index of an element, and that epilogue involves a linear search through 17000 elements, then it's not really O(log n) anymore, is it?

One way to avoid such a lengthy linear search is with some speculative skipping and backtracking — basically another kind of binary search to find the boundary.

I think, however, that you would be better off with a more appropriate data structure. I propose using an order statistic tree.

Order statistic tree

An order statistic tree is basically a search tree with some additional bookkeeping for the size of the subtree at each node. Here, I'll present a binary search tree with no rebalancing.

This is basically a variant of the data structure described in Wikipedia, but each node may represent multiple copies of the same element. It supports operations insert(datum), count(datum), indexOf(datum), and lastIndexOf(datum) in O(log n) time — as long as the tree is balanced. Fancier variants include B-trees and red-black trees.

public class OrderStatisticTree<T extends Comparable<T>> {
    /**
     * A binary tree node with bookkeeping for the size of the subtree (the
     * number of elements represented by this node, plus the sizes of all left
     * and right descendants).
     */
    private class Node {
        final T datum;
        Node left, right, parent;
        int size;

        Node(Node parent, T datum, int size) {
            this.parent = parent;
            this.datum = datum;
            this.incrSize(size);
        }

        void incrSize(int delta) {
            for (Node n = this; n != null; n = n.parent) {
                n.size += delta;
            }
        }
    }

    private Node root;

    public void insert(T datum) {
        this.insert(datum, 1);
    }

    public void insert(T datum, int numCopies) {
        if (this.root == null) {
            this.root = new Node(null, datum, numCopies);
            return;
        }
        Node n = this.root;
        do {
            int cmp = n.datum.compareTo(datum);
            if (cmp < 0) {
                if (n.right == null) {
                    n.right = new Node(n, datum, numCopies);
                    break;
                } else {
                    n = n.right;
                }
            } else if (cmp > 0) {
                if (n.left == null) {
                    n.left = new Node(n, datum, numCopies);
                    break;
                } else {
                    n = n.left;
                }
            } else {
                n.incrSize(numCopies);
                break;
            }
        } while (true);
    }

    public int size() {
        return (this.root == null) ? 0 : this.root.size;
    }

    public int count(T datum) {
        return this.count(this.find(datum));
    }

    private int count(Node n) {
        if (n == null) return 0;
        int lSize = (n.left  == null) ? 0 : n.left.size;
        int rSize = (n.right == null) ? 0 : n.right.size;
        return n.size - lSize - rSize;
    }

    public int indexOf(T datum) {
        return this.indexOf(this.find(datum));
    }

    private int indexOf(Node n) {
        if (n == null) return -1;
        int index = (n.left == null) ? 0 : n.left.size;
        for (; n != this.root; n = n.parent) {
            if (n == n.parent.right) {
                index += n.parent.size - n.size;
            }
        }
        return index;
    }

    public int lastIndexOf(T datum) {
        Node n = this.find(datum);
        int index = this.indexOf(n);
        return (index < 0) ? index : index + this.count(n) - 1;
    }

    private Node find(T datum) {
        for (Node n = this.root; n != null; ) {
            int cmp = n.datum.compareTo(datum);
            if (cmp < 0) {
                n = n.right;
            } else if (cmp > 0) {
                n = n.left;
            } else {
                return n;
            }
        }
        return null;
    }
}

Answer 2

There are three alternatives you should consider. Depending on circumstances, I have used all three.

The most simple, is to comment the block.

while (lastSucceedingIndex < tailIndex && (array[++lastSucceedingIndex] == key)) {
    //loop condition terminates when key is not found, or data runs out.
}
lastSucceedingIndex--;

The comment should shut down the error.

The second approach is to simplify the loop condition to match your code and to make the dependent code part of the loop. The pre-increment is essentially your "work" which should be in the block... but, because it is a pre-increment, it is messy... Still, your code would become...

while (lastSucceedingIndex < tailIndex) {
    lastSucceedingIndex++;
    if (array[lastSucceedingIndex] != key) {
        break;
    }
}
lastSucceedingIndex--;

That's still not as neat as I would like, but it reduces the complexity of the while condition and makes the break-out process more apparent.

This last alternative is simpler in other ways:

while (lastSucceedingIndex < tailIndex && array[lastSucceedingIndex + 1] == key) {
    lastSucceedingIndex++;
}

Now there is no need for the corrective decrement.