Binary Chop, Functional

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