Binary Chop


Sister

DaveThomas suggests practicing programming and offers 'Kata' (practice problems) to encourage the activity. Here is a recent Kata.

The Kata is to write a binary chop, often called binary search. Dave offered the following specification and included test data which I've converted to tables.


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

Here is the test data I used when developing my methods. Feel free to add to it. The tests assume that array indices start at zero.

The table has been modifed to run all of Ward's versions. Try this yourself with http:run.cgi.

eg.BinaryChop
key array mon() tue() wed() thr() fri()
3   -1 -1 -1 -1 -1
3 1 -1 -1 -1 -1 -1
1 1 0 0 0 0 0
1 1, 3, 5 0 0 0 0 0
3 1, 3, 5 1 1 1 1 1
5 1, 3, 5 2 2 2 2 2
0 1, 3, 5 -1 -1 -1 -1 -1
2 1, 3, 5 -1 -1 -1 -1 -1
4 1, 3, 5 -1 -1 -1 -1 -1
6 1, 3, 5 -1 -1 -1 -1 -1
1 1, 3, 5, 7 0 0 0 0 0
3 1, 3, 5, 7 1 1 1 1 1
5 1, 3, 5, 7 2 2 2 2 2
7 1, 3, 5, 7 3 3 3 3 3
0 1, 3, 5, 7 -1 -1 -1 -1 -1
2 1, 3, 5, 7 -1 -1 -1 -1 -1
4 1, 3, 5, 7 -1 -1 -1 -1 -1
6 1, 3, 5, 7 -1 -1 -1 -1 -1
8 1, 3, 5, 7 -1 -1 -1 -1 -1


Dave suggests writing this program differently every day for a week. For a week. I've done that. He also suggests keeping track of errors, which I did and summarize as follows.

  • Monday
    • off by one
    • sense of test
    • operator precedence
    • leading blanks (in fit)
    • null value (in fit)
  • Tuesday
    • type incompatibility
    • sense of test
  • Wednesday
    • off by one
    • offset
    • sense of test
    • case analysis
  • Thursday
    • interface
  • Friday
    • no errors

Wednesday was a tough day. Here are the kind of results I was getting while working on my third implementation which was the first to use recursion.

Notice that fit kept on running even as I repeatedly exhausted the runtime stack. This allowed me to study the distribution of errors and go directly to the source of my error. Then it worked perfectly.

See the source.

 

Last edited April 22, 2003
Return to WelcomeVisitors