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

java.lang.Object
  org.apache.commons.functor.example.kata.two.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: 1171255 $ $Date: 2011-09-15 22:27:39 +0200 (Thu, 15 Sep 2011) $

Author:

Rodney Waldhoff

Constructor Summary

TestBinaryChop()

Method Summary

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 Function 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 Function implemenation holds the "continuation" state.