org.apache.commons.functor.example.kata.two

## Class TestBinaryChop

• ```public class TestBinaryChop
extends Object```
Examples of binary search implementations. A binary search algorithm is the same strategy used in that number guessing game, where one player picks a number between 1 and 100, and the second player tries to guess it. Each time the second player guesses a number, the first player tells whether the chosen number is higher, lower or equal to the guess. An effective strategy for this sort of game is always guess the midpoint between what you know to be the lowest and highest possible number. This will find the number in log2(N) guesses (when N = 100, this is at most 7 guesses). For example, suppose the first player (secretly) picks the number 63. The guessing goes like this: P1> I'm thinking of a number between 1 and 100. P2> Is it 50? P1> Higher. P2> 75? P1> Lower. P2> 62? P1> Higher. P2> 68? P1> Lower. P2> 65? P1> Lower. P2> 63? P1> That's it. Dave Thomas's Kata Two asks us to implement a binary search algorithm in several ways. Here we'll use this as an opportunity to consider some common approaches and explore some functor based approaches as well. See http://pragprog.com/pragdave/Practices/Kata/KataTwo.rdoc,v for more information on this Kata.
Version:
\$Revision: 1541658 \$ \$Date: 2013-11-13 19:54:05 +0100 (Mi, 13 Nov 2013) \$
• ### Constructor Summary

Constructors
Constructor and Description
`TestBinaryChop()`
• ### Method Summary

Methods
Modifier and Type Method and Description
`void` `testBuiltIn()`
In practice, one would most likely use the binary search method already available in java.util.Collections, but that's not really the point of this exercise.
`void` `testIterative()`
Here's a basic iterative approach.
`void` `testIterativeWithInvariants()`
`void` `testIterativeWithInvariantsAndAssertions()`
`void` `testRecursive()`
A recursive version of that implementation uses method parameters to track the upper and lower bounds.
`void` `testRecursive2()`
One fun functional approach is to "slice" up the list as we search, looking at smaller and smaller slices until we've found the element we're looking for.
`void` `testTailRecursive()`
We can use the Algorithms.recuse method to implement that as tail recursion.
`void` `testTailRecursive2()`
We can do that using tail recursion as well.
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### TestBinaryChop

`public TestBinaryChop()`
• ### Method Detail

• #### testBuiltIn

`public void testBuiltIn()`
In practice, one would most likely use the binary search method already available in java.util.Collections, but that's not really the point of this exercise.
• #### testIterative

`public void testIterative()`
Here's a basic iterative approach. We set the lower or upper bound to the midpoint until there's only one element between the lower and upper bound. Then the lower bound is where the element would be found if it existed in the list. We add an additional comparision at the end so that we can return -1 if the element is not yet in the list.
• #### testIterativeWithInvariants

`public void testIterativeWithInvariants()`
• #### testIterativeWithInvariantsAndAssertions

`public void testIterativeWithInvariantsAndAssertions()`
• #### testRecursive

`public void testRecursive()`
A recursive version of that implementation uses method parameters to track the upper and lower bounds.
• #### testTailRecursive

`public void testTailRecursive()`
We can use the Algorithms.recuse method to implement that as tail recursion. Here the anonymous NullaryFunction implemenation holds this itermediate state, rather than the VM's call stack. Arguably this is more like a continuation than tail recursion, since there is a bit of state to be tracked.
• #### testRecursive2

`public void testRecursive2()`
One fun functional approach is to "slice" up the list as we search, looking at smaller and smaller slices until we've found the element we're looking for. Note that while any given call to this recursive function may only be looking at a sublist, we need to return the index in the overall list. Hence we'll split out a method so that we can pass the offset in the original list as a parameter. With all of the subList creation, this approach is probably less efficient than either the iterative or the recursive implemenations above.
• #### testTailRecursive2

`public void testTailRecursive2()`
We can do that using tail recursion as well. Again, the anonymous NullaryFunction implemenation holds the "continuation" state.