I think you just have to drop the stop condition, i.e. in the classical case the algorithm stops when the search string is found. Here you have to look on until the upper and lower ends of the search interval are reduced to neighboring elements (i.e. no further halving step is possible). The upper element is the the one you want in the case of $beg, the lower element the one in case of $end.

Small special case: If the search interval contracts to elements 0 and 1, $beg might start at 0. Other way round for $end