This is a continuation of the KataTwoVariation1 posting where we are trying different methods of implementing a binary search. In the first version we discussed an iterative approach and using loop invariants. In this second installment we cover the the recursive versions. (see Kata Two for background information)

Variation #2: Recursive

This is a standard recursive implementation of the algorithm we looked at in KataTwoVariation1. This version determines which half of the array contains our target value and recurses on the appropriate half of the array.

Code

Here’s the code …

  def chop_recursive(target, list, offset=0)
    if list.size <= 1
      (list[0] == target) ? offset : -1
    end
    mid = list.size/2
    if list[mid] > target
      chop_recursive(target, list[0...mid], offset)
    else
      chop_recursive(target, list[mid..-1], offset+mid)
    end
  end

  class TestChopRecursive < Test::Unit::TestCase
    alias chop chop_recursive
    include ChopTests
  end

Problems Encountered

In writing this version, I encountered the following issues …

• I had a problem where I miscalculated the array fragment to recurse on. The miscalculation led to a recursive call where the size of the array wasn’t decreased, and led to infinite recursion.
• Since a copy of the array is passed, we lose information on the position of the target value in the full array. I had to pass in the offset of the of start of the array fragment to correct for this.
• I refactored the method to return nil (instead of -1) when the target value was not found. I decided that it didn’t help improve the logic in any way, so I put the -1 return value back in.
• There was a performance bug where I searched both branches of the array (and then returned the one that matched).
• The size==1 test really bugs me. I made several (unsuccessful) attempts to get rid if it. (But see the next item)
• The original version of the recursive version started with …

    def chop_recursive(target, list, offset=0)
      return -1 if list.empty?
      return offset if list[0] == target
      return -1 if list.size == 1
      ...
  

  This version tests list[0] agains target at the entry to every recursive call. This is wrong. I should only test when the list is down to one element. This defect made it into the original posting and it wasn’t until I was reviewing the code for the CPS post that I discovered the error. It also might explain my discomfort with the list.size==1 test. It was actually the list.empty? test that was incorrect and the size check evolved to list.size <= 1.

Variation #3: Recursive with Explicit Limits

In variation 2, I decided to pass a copy of the sub-array in each recursive call. This is an expensive operation, but I was thinking that I could avoid passing around explicit limits this way. However, it turned out that I still needed to pass the offset, negating much of the advantage.

In variation 3 we will avoid makeing array copies by always passing the original array around. Instead of arrays, we will explicitly pass the hi/lo limits of the sub-array in the recursive call.

I think this version is not only more efficient than variation 2, it is also easier to read and understand.

Notice that the recursive call in this version takes 4 parameters, so I created a helper function (rchoplim) with the proper signature to do the recursion.

Code

Here’s the code …

  def chop_recursive_passing_limits(target, list)
    rchoplim(target, list, 0, list.size)
  end

  def rchoplim(target, list, lo, hi)
    if (hi-lo) <= 1
      list[lo] == target ? lo : -1
    else
      mid = (lo+hi) / 2
      if list[mid] > target
        rchoplim(target, list, lo, mid)
      else
        rchoplim(target, list, mid, hi)
      end
    end
  end

  class TestChopRecursiveWithLimits < Test::Unit::TestCase
    alias chop chop_recursive_passing_limits
    include ChopTests
  end

Problems Encountered

There were no problems encountered while implementing Variation 3. I think the simpler logic helped (plus I worked out a number of bugs in Variation 2).

Things to Come

In the next installment, we will explore a CPS (Continuation Passing Style) implementation.