It's not a problem for a binary search that the value does not exist in the tree. It will find the nearest place for it.

Here is an excerpt from the binary search documentation:

use Search::Binary;
$pos = binary_search($min, $max, $val, $read, $handle, [$size]);
[download]

"binary_search" implements a generic binary search algo­rithm returning the position of the first record whose index value is greater than or equal to $val.