Dave Thomas maintains a blog of “Code Kata’s”. He describes a code kata as being a practice session for practicing coding skills:

Each is a short exercise (perhaps 30 minutes to an hour long). Some involve programming, and can be coded in many different ways. Some are open ended, and involve thinking about the issues behind programming. These are unlikely to have a single correct answer.

Here are two of my solutions for kata two using Ruby. The first uses recursion and the second uses an iterative approach.

Recursive solution …

# Recursive implementation def chop(target, values) # Special handling for zero and single element arrays return -1 if values.empty? return ((target == values[0]) ? 0 : -1) if values.length == 1 # Try the bottom half first pos = chop(target, values[0, values.length/2]) return pos if pos != -1 # Then the upper half ... remember that the returned # position is relative to the middle of the array. pos = chop(target, values[values.length/2, values.length-1]) return pos + (values.length/2) if pos != -1 # Didn't find what we were looking for return -1 end

Iterative solution …

# Iterative implementation def chop(target, values) start = 0 stop = values.length # stop indexes one past the end of the array # loop until something is found or until we # run out of elements to search while start != stop # Find the middle mid = start + (stop - start) / 2 # Check to see if we got lucky return mid if values[mid] == target # Not this time ... so lets see which half it might be in if target < values[pos] stop = mid else start = mid + 1 end end # Didn't find what we were looking for return -1 end