Binary Chop

DaveThomas offers this specification for binary chop, an exercise in programming described more fully here.

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 data I used when developing my methods. Feel free to add to it. The tests assume that array indices start at zero.

eg.BinaryChop
key array result()
3   -1
3 1 -1 
java.lang.StackOverflowError
	<>
1 1 0
1 1, 3, 5 0
3 1, 3, 5 1
5 1, 3, 5 2
0 1, 3, 5 -1
2 1, 3, 5 -1 
java.lang.StackOverflowError
	<>
4 1, 3, 5 -1 
java.lang.StackOverflowError
	<>
6 1, 3, 5 -1 
java.lang.StackOverflowError
	<>
1 1, 3, 5, 7 0
3 1, 3, 5, 7 1
5 1, 3, 5, 7 2
7 1, 3, 5, 7 3
0 1, 3, 5, 7 -1
2 1, 3, 5, 7 -1 
java.lang.StackOverflowError
	<>
4 1, 3, 5, 7 -1 
java.lang.StackOverflowError
	<>
6 1, 3, 5, 7 -1 
java.lang.StackOverflowError
	<>
8 1, 3, 5, 7 -1 
java.lang.StackOverflowError
	<>

Last edited April 14, 2003