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

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.

• Please clarify the intended purpose of your code. Right now, the question looks a bit hypothetical, and arguably off-topic as a result. Furthermore, I suspect that your code is buggy, but I can't tell because you haven't stated the purpose. – 200_success May 10 '15 at 9:51
• I tried to make it more clear. I don't know how to come up with a better title though. I asked a question and the answer I got was in line with what I wanted, so that person completely understood my question. – Joop May 10 '15 at 10:06
• I don't know whether this question is really suited for Code Review. It asks about general practice for a very specific piece of code. I don't know whether it would be on-topic on SO or Programmers.SE but I have the feeling that the question is really borderline at best for Code Review :/ – Morwenn May 10 '15 at 13:10
• I asked it because it's directly related to Best practices and design pattern usage. Now that I know the different ways how to write it I can clearly see what is the best practice. – Joop May 10 '15 at 13:13
• Thank you for adding the use case. While the question could still be improved by showing the surrounding code, it is no longer so unclear that it needs to remain closed. – 200_success May 10 '15 at 23:21

## Goals

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;
}
}


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.

• I don't believe that your solutions are equivalent to the original. – 200_success May 10 '15 at 9:49
• I'm sorry to say @200_success but you're trying to make this site better by putting this post on hold, but then you make a comment which is clearly a bad comment. You "believe" that something is not equivalent without explaining why you believe this is the case. This comment is almost useless since it only dismisses a good answer without explanation why, at the very least not constructive. – Joop May 10 '15 at 10:08
• You are right that I should have explained my actions better. I've added an "answer" that explains my concerns. – 200_success May 10 '15 at 19:38
• Thank you. I will do my best to change it and understand your points so it won't happen in the future. – Joop May 10 '15 at 19:53