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
[/sourcecode]