My take on TDD & binary search

2012-01-08T16:06:2901:00:00

Jason Gorman blogged about TDD and binary search. He also followed up with a 2nd take.

The question Jason raised was, will you end up with binary search using TDD. Jason also mentions Uncle Bob's transformation priority premise which is an interesting idea.
Looking at Jason's attempts I thought that maybe you could take even smaller steps, I couldn’t resist to try so here’s how I did it.

My first test is the same as Jason's:

[Test]
public void When_key_is_not_found_index_returned_is_minus_one()
{
    Assert.AreEqual(-1, new BinarySearch().FindIndexOf(new[] { 0 }, 1));
}

This test is easily solved by returning a constant (-1)

public int FindIndexOf(int[] values, int toFind)
{
    return -1;
}

Next test, lets try to find a value in a list.

[Test]
public void Index_of_key_value_1_in_list_1_is_0()
{
    Assert.AreEqual(0, new BinarySearch().FindIndexOf(new[] { 1 }, 1));
}

Which I solved with introducing an if statement.

public int FindIndexOf(int[] values, int toFind)
{
    const int index = 0;
    if (values[index] == toFind)
        return index;
    return -1;
}

Test number three, lets try a list with 2 numbers.

[Test]
public void Index_of_key_value_2_in_list_1_2_is_1()
{
    Assert.AreEqual(1, new BinarySearch().FindIndexOf(new[] { 1, 2 }, 2));
}

Which I solved with transforming the index constant to scalar, or is it a constant+ ?

public int FindIndexOf(int[] values, int toFind)
{
    var index = values.Length - 1;
    if (values[index] == toFind)
        return index;
    return -1;
}

So next test, how do I break this code?
Well, I can break this by looking for a 1 in a list with numbers 1,2. This is a pretty small step I think.

[Test]
public void Index_of_key_value_1_in_list_1_2_is_0()
{
    Assert.AreEqual(0, new BinarySearch().FindIndexOf(new[] { 1, 2 }, 1));
}

In the implementation code I renamed index to upperBound and added another if statement to check the value in the lower bound of the list.

public int FindIndexOf(int[] values, int toFind)
{
    var upperBound = values.Length - 1;
    if (values[upperBound] == toFind)
        return upperBound;
    const int lowerBound = 0;
    if (values[lowerBound] == toFind)
        return lowerBound;
    return -1;
}

Which I then refactored into

public int FindIndexOf(int[] values, int toFind)
{
    const int lowerBound = 0;
    var upperBound = values.Length - 1;
    return FindIndexOf(values, toFind, lowerBound, upperBound);
}

private int FindIndexOf(int[] values, int toFind, int lowerBound, int upperBound)
{
    if (values[upperBound] == toFind)
        return upperBound;
    if (values[lowerBound] == toFind)
        return lowerBound;
    return -1;
}

So what is the next test? I think the simplest test would be 3 numbers in a list and we should find the middle number.

[Test]
public void Index_of_key_value_2_in_list_1_2_3_is_1()
{
    Assert.AreEqual(1, new BinarySearch().FindIndexOf(new[] { 1, 2, 3 }, 2));
}

There is not much point in checking only the first and last value in a list that has more than 2 items in it.
So, lets split the list in half and try again.

private int FindIndexOf(int[] values, int toFind, int lowerBound, int upperBound)
{
    if (upperBound - lowerBound <= 1)
    {
        if (values[upperBound] == toFind)
            return upperBound;
        if (values[lowerBound] == toFind)
            return lowerBound;
        return -1;
    }
    return FindIndexOf(values, toFind, upperBound / 2, upperBound);
}

Was this step to far? I'm not sure.
Anyway, the next step is pretty obvious, the solution only handle the upper half of the list so far.
So lets write a test that expose that flaw, find the first element in a list when there are more than two items in the list.

[Test]
public void Index_of_key_value_1_in_one_1_2_3_is_0()
{
    Assert.AreEqual(0, new BinarySearch().FindIndexOf(new[] { 1, 2, 3 }, 1));
}

Yup, that failed alright, FindIndexOf returned -1.
Lets fix the code so it searches the lower half of the list too.

private int FindIndexOf(int[] values, int toFind, int lowerBound, int upperBound)
{
    if (upperBound - lowerBound <= 1)
    {
        if (values[upperBound] == toFind)
            return upperBound;
        if (values[lowerBound] == toFind)
            return lowerBound;
        return -1;
    }
    var middle = (upperBound - lowerBound) / 2 + lowerBound;
    if (toFind < values[middle])
        return FindIndexOf(values, toFind, lowerBound, middle);
    return FindIndexOf(values, toFind, middle, upperBound);
}

Now the test passes.
And I believe the code looks like an implementation of binary search.

Lets try the algorithm with a large list just to be sure it works on large lists too.

[Test]
public void A_large_array()
{
    var values = Enumerable.Range(1, 100000000).ToArray();
    Assert.AreEqual(14, new BinarySearch().FindIndexOf(values, 15));
}

Yes, it passed!

So I ended up with binary search, but was it because I knew the algorithm or did the tests and the transformation priority premise lead me there?

Morgan Persson

My take on TDD & binary search