An algorithm for searching
in a binary search
tree using two-way comparisons is presented.
The number of comparisons required by this
algorithm is only one more than when
using three-way comparisons.
Since most high-level
programming languages do not supply
three-way comparisons, the number of comparisons used
de facto are reduced by a factor of two.
We give experimental results to indicate the speedup
that may be achieved by the presented algorithm.
Full paper (postscript)
Full paper (pdf)