Refactor Preconditon Pattern

The following is my implementation of the insertion of a B-Tree storing (int,double) pairs:

class BTree {
    class Node {
        ArrayList<Pair> data;
        ArrayList<Node> children;
        // ...
    }

    class Pair {
        int k;
        double v;
    }

    void insert(int k, double v) {
        Node currNode = root;
        while (!currNode.isLeaf()) {
            if (currNode.contains(k)) return; // duplicate insert
            currNode = currNode.forward(k); // go to promising child
        }
        currNode.insert(k, v);
        if (currNode.isOverflow()) {
            handleOverflow(currNode);
        }
    }

    // ...
}

Just to clarify the B-Tree properties for list-based implementation:

For any node, let:

• a(i) := children.get(i).data.get(j).k for all j (i.e. all key in i-th child node)
• b(i) := data.get(i).k (i.e. key of i-th data pair)

a(i) < b(i) < a(i+1) is guaranteed.

In order to implement Node.contains(int k), I have to do a binary search on data. In order to implement Node.forward(int k), I have to do the same binary search again.

Please give me some hints on how the redundant binary search could be saved.