This time I decided to not use any previous versions as a starting point. Again I made mistakes that ended up causing endless loops on some of the test cases. The previous solution was somewhat in the functional style, using recursion instead of looping. I went further this time and passed array slices rather than indices for good measure.

No doubt in my mind this is the worst implementation so far. It's verbose and hard to understand. It has special case checks. It uses a lot of stack for storing array slices. I particularly dislike the special handling needed for the second recursive call — when the top half of the array is searched, a correction must be applied to the index for the whole array.

I've had one lesson hammered into my skull. When the array slice gets to two elements, size/2 stays at one. Hence, when the
value is in the first half of the array, it is vital to search the array up to the item *before* the midpoint. It's surprising that this
is required for correctness as well as in order to avoid
unnecessary work.

module BinChopper def chop(n,a) if a.empty? return -1 end if n == a.midpoint_value return a.midpoint end if a.size == 1 return -1 elsif n < a.midpoint_value return chop(n, a[0 .. a.midpoint - 1]) elsif n > a.midpoint_value return apply_correction(a.midpoint, chop(n, a[a.midpoint + 1 .. a.size - 1])) end end def apply_correction(mid, target) if target < 0 return target else return 1 + mid + target end end end class Array def midpoint return size / 2 end def midpoint_value return self[midpoint] end end