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) -> intYou 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.
See the source.