Kata Two -- Karate Chop

A binary chop (sometimes called the more prosaic binary search) finds the position of value in a sorted array of values. It achieves some efficiency by halving the number of items under consideration each time it probes the values: in the first pass it determines whether the required value is in the top or the bottom half of the list of values. In the second pass in considers only this half, again dividing it in to two. It stops when it finds the value it is looking for, or when it runs out of array to search. Binary searches are a favorite of CS lecturers.

This Kata is straightforward. Implement a binary search routine (using the specification below) in the language and technique of your choice. Tomorrow, implement it again, using a totally different technique. Do the same the next day, until you have five totally unique implementations of a binary chop. (For example, one solution might be the traditional iterative approach, one might be recursive, one might use a functional style passing array slices around, and so on).

Goals

This Kata has three separate goals:

1. As you’re coding each algorithm, keep a note of the kinds of error you encounter. A binary search is a ripe breeding ground for "off by one" and fencepost errors. As you progress through the week, see if the frequency of these errors decreases (that is, do you learn from experience in one technique when it comes to coding with a different technique?).
2. What can you say about the relative merits of the various techniques you’ve chosen? Which is the most likely to make it in to production code? Which was the most fun to write? Which was the hardest to get working? And for all these questions, ask yourself "why?".
3. It’s fairly hard to come up with five unique approaches to a binary chop. How did you go about coming up with approaches four and five? What techniques did you use to fire those "off the wall" neurons?

Specification

Write a binary chop method that takes an integer search target and a sorted array of integers. It should return the integer index of the target in the array, or -1 if the target is not in the array. The signature will logically be:

   chop(int, array_of_int)  -> int

You can assume that the array has less than 100,000 elements. For the purposes of this Kata, time and memory performance are not issues (assuming the chop terminates before you get bored and kill it, and that you have enough RAM to run it).

Test Data

Here is the Test::Unit code I used when developing my methods. Feel free to add to it. The tests assume that array indices start at zero. You’ll probably have to do a couple of global search-and-replaces to make this compile in your language of choice (unless your enlightened choice happens to be Ruby).

  def test_chop
    assert_equal(-1, chop(3, []))
    assert_equal(-1, chop(3, [1]))
    assert_equal(0,  chop(1, [1]))
    #
    assert_equal(0,  chop(1, [1, 3, 5]))
    assert_equal(1,  chop(3, [1, 3, 5]))
    assert_equal(2,  chop(5, [1, 3, 5]))
    assert_equal(-1, chop(0, [1, 3, 5]))
    assert_equal(-1, chop(2, [1, 3, 5]))
    assert_equal(-1, chop(4, [1, 3, 5]))
    assert_equal(-1, chop(6, [1, 3, 5]))
    #
    assert_equal(0,  chop(1, [1, 3, 5, 7]))
    assert_equal(1,  chop(3, [1, 3, 5, 7]))
    assert_equal(2,  chop(5, [1, 3, 5, 7]))
    assert_equal(3,  chop(7, [1, 3, 5, 7]))
    assert_equal(-1, chop(0, [1, 3, 5, 7]))
    assert_equal(-1, chop(2, [1, 3, 5, 7]))
    assert_equal(-1, chop(4, [1, 3, 5, 7]))
    assert_equal(-1, chop(6, [1, 3, 5, 7]))
    assert_equal(-1, chop(8, [1, 3, 5, 7]))
  end

Comments

[grow taller]

key was not in the list should return the location where the item would be inserted as a negative value.

[ClubPenguinCheats]

I'm thinking of optimising for code space and for memory for the next two, and seeing where it takes me. Perhaps have self modifying code.

[outis]

@Mattias: other options include:

1. concurrency: for a slice, spawns threads to check each case for the slice. The successful thread will go on to spawn more threads. This will create O(lg(len(array))) threads)
2. continuations, which turn your brain inside-out. Here's a partial solution in Scheme, so as not to spoil it:

    (define (chop x items)
      (define (return x) x)
      (let* ((lohi (call/cc (lambda (k)
                             (set! return k)
                             (cons 0 (- (vector-length items) 1)))))
             (lo (car lohi))
             (hi (cdr lohi)))
        ...
    ) )

[Mattias]

Has anyone been able to come up with another approach to solving this problem other than iterative and recursive?

I have three solutions where two of them are rather similar.

1. Iterative.
2. Split array in two, lower and upper half. If the value we're looking for is in the lower part, split that array in two and continue looking. If the value isn't in the lower part but is in the upper part, split the upper part in two and continue looking. If not found in either part, return -1.
I've implemented this algorithm both as a loop that iterates until there is only one element in the list and recursively where a method keeps calling itself until there is only one element left in the list.

I don't have a blog or anything where I can post my solutions and I assume you don't want me to post it here as it would totally clutter the blog.

My solutions are in Java by the way.

It would be fun if someone found another way of impelementing this algorithm.

Regards, Mattias

[Stephen Doyle]

My recursive and iterative solutions in Ruby ...
http://softwareramblings.com/2009/11/codekata-kata-two-solution.html

[www.facebook.com/profile.php?id=505631250]

Here's an iterative solution of mine that I don't entirely hate... http://gist.github.com/224727

[Matt Ridenour]

I was reading Chad Fowler's "The Passionate Programmer" and he mentions this site in the book. It's a great idea; I thought I'd give it a go.

Here's a recursive solution in Ruby:

http://blog.mattbot.net/2009/09/19/codekata-practice-for-programmers/

[Emtucifor]

Kent Mentolado,

Look again, that would be -1. His answer is one-based.

[Kent Mentolado]

SenseiJae,

What if the value should be inserted at the first place? You return -0?

[SenseiJae]

Academically, I was taught that a binary search on a list where the key was not in the list should return the location where the item would be inserted as a negative value.

For example, bsearch(4, [0, 1, 2, 3, 5, 6, 7])
Should return -5

A subtly more challenging problem.

[Raul Jara]

These are great katas, and I really like the concept of katas in general. I'm also pretty new to programming, so solving this was my first experience with Test::Unit. It was _very_ helpful.

On my first go, however, I was able to write a method that passed the tests without being a true solution. I wrote an additional test with an arbitrarily large array that would be much harder to fool. Here it is, for any other ruby beginners out there

def test_chop_with_large_array
large_array_length = 34519 #or any arbitrary large number
count_by = 4 #or any even, non-zero number
large_array = []
(1..large_array_length).each{|x| large_array << x * count_by}
(1..large_array_length).each{|x| assert_equal( (x - 1), chop(x * count_by, large_array))}
(1..large_array_length).each{|x| assert_equal( -1, chop(x * count_by + 1, large_array))}
end

[nazlfrag]

Nice challenge, I've done two implementations so far, iterative & recursive. I'm thinking of optimising for code space and for memory for the next two, and seeing where it takes me. Perhaps have self modifying code. It's such a deceptively simple algorithm but I'm sure theres dozens of unique approaches.

[Rulas]

This is a nice one, I'm using C# and I just get one solution right now, as soon as I have a little time I´ll continue...This is very fun, nice idea this codekata blog