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