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
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> 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.
for more information on this Kata.
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
We add an additional comparision at the end so
that we can return -1 if the element is not yet
in the list.
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.
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
With all of the subList creation, this approach
is probably less efficient than either the iterative
or the recursive implemenations above.