Lower bound from the right in a B-tree

I have a B-tree and I'd like to, given an arbitrary parameter key, figure out what the greatest data key less then or equal to the parameter key. In other words, I want it to look to the left to figure out what key it should use in O(log n).

I've already modified the implementation of lower_bound in C code.

#define ORDER 3
static int compare(const int a, const int b) { return a > b; }
struct node { unsigned size; int key[ORDER - 1]; };
struct branch { struct node base, *child[ORDER]; };
struct ref { struct node *node; unsigned height, idx; };
struct tree { struct node *node; unsigned height; };

static struct ref lower(const struct tree tree, const int x) {
    struct ref lo, found;
    found.node = 0;
    if(!tree.node) return found;
    for(lo.node = tree.node, lo.height = tree.height; ;
        lo.node = ((const struct branch *)(const void *)lo.node)->child[lo.idx],
        lo.height--) {
        unsigned hi = lo.node->size; lo.idx = 0;
        if(!hi) continue;
        do {
            const unsigned mid = (lo.idx + hi) / 2; /* Will not overflow. */
            if(compare(x, lo.node->key[mid]) > 0) lo.idx = mid + 1;
            else hi = mid;
        } while(lo.idx < hi);
        if(lo.idx < lo.node->size) { /* Within bounds, record the current. */
            found = lo;
            if(compare(x, lo.node->key[lo.idx]) > 0) break;
        }
        if(!lo.height) break;
    }
    return found;
}

static int tree_lower_or(const struct tree tree,
    const int key, const int default_value) {
    struct ref ref;
    return (ref = lower(tree, key)).node
        && ref.idx < ref.node->size ? ref.node->key[ref.idx] : default_value;
}

#include <stdio.h>

int main(void) {
    struct node node[] = { { 2, {1,2} }, { 2, {5, 6} } };
    struct branch root = { { 1, {4} }, {node, node+1} };
    const struct tree tree = { &root.base, 1 };
    int i;
    for(i = 0; i < 8; i++)
        printf("%d->%d%s", i, tree_lower_or(tree, i, 0), i < 7 ? ", " : "\n");
    return 0;
}

This uses the example in std::lower_bound, data = {1, 2, 4, 5, 5, 6}. (Note that my B-tree's keys are strongly increasing, so I can't have two 5s.) It prints out 0->1, 1->1, 2->2, 3->4, 4->4, 5->5, 6->6, 7->0, which is x->next x in set or 0.

This is not quite what I want. The upper_bound is also not quite what I want, but close.

I want a lower bound from the right instead of the left, x->last x in set or 0.

Is there a name for this and how to I modify the lower above to give this result?

The way I would implement this is:

• get the upper_bound
• get the previous element (if any)
• A) if there is a previous element and the element is == the key you are searching for, return it
• B) otherwise, return the upper bound

In general you either care about the element directly before the upper_bound or about the upper_bound.