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

[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

[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.

[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

[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.

[Kent Mentolado]

SenseiJae,

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