Bug in Eytzinger lower_bound() for values larger than all elements #394

Problem

A binary search on the Eytzinger layout in §12.1 fails when the query value x is greater than every element in t. In this case, the search ends up returning t[0], whereas users would typically expect t[n] (i.e. the end position).

Possible Solution

The issue occurs when k is of the form $2^m - 1$, meaning that the search path never takes a left branch. We can detect this case using

(k & k.wrapping_add(1)) == 0

When this condition is true, we want to shift by 1; otherwise, we want to shift by k.trailing_ones() + 1.

This can be implemented in a branch-free manner:

let mask = if (k & k.wrapping_add(1)) == 0 { 0 } else { !0 }; // this branch should be optimized away by the compiler
k >>= (k.trailing_ones() & mask) + 1;