Binary Search improvements in C# track

Exercism
1

I’d like to improve the C# track implementation of the Binary Search exercise.

The idea is to prevent tests passing if we don’t implement a real binary search, like :

public static int index Find(int[] input, int value) => Array.IndexOf(input, value);

My proposition is to change the signature of the function :

public static (int index, int iterationsCount) Find(int[] input, int value)

and update the tests :

public class BinarySearchTests
{
    [Fact]
    public void Finds_a_value_in_an_array_with_one_element()
    {
        Assert.Equal((0, 1), BinarySearch.Find([6], 6));
    }

    [Fact]
    public void Finds_a_value_in_the_middle_of_an_array()
    {
        Assert.Equal((3, 1), BinarySearch.Find([1, 3, 4, 6, 8, 9, 11], 6));
    }

    [Fact]
    public void Finds_a_value_at_the_beginning_of_an_array()
    {
        Assert.Equal((0, 3), BinarySearch.Find([1, 3, 4, 6, 8, 9, 11], 1));
    }

    [Fact]
    public void Finds_a_value_at_the_end_of_an_array()
    {
        Assert.Equal((6, 3), BinarySearch.Find([1, 3, 4, 6, 8, 9, 11], 11));
    }

    [Fact]
    public void Finds_a_value_in_an_array_of_odd_length()
    {
        Assert.Equal((9, 2), BinarySearch.Find([1, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 634], 144));
    }

    [Fact]
    public void Finds_a_value_in_an_array_of_even_length()
    {
        Assert.Equal((5, 1), BinarySearch.Find([1, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377], 21));
    }

    [Fact]
    public void Identifies_that_a_value_is_not_included_in_the_array()
    {
        Assert.Equal((-1, 3), BinarySearch.Find([1, 3, 4, 6, 8, 9, 11], 7));
    }

    [Fact]
    public void A_value_smaller_than_the_array_s_smallest_value_is_not_found()
    {
        Assert.Equal((-1, 3), BinarySearch.Find([1, 3, 4, 6, 8, 9, 11], 0));
    }

    [Fact]
    public void A_value_larger_than_the_array_s_largest_value_is_not_found()
    {
        Assert.Equal((-1, 3), BinarySearch.Find([1, 3, 4, 6, 8, 9, 11], 13));
    }

    [Fact]
    public void Nothing_is_found_in_an_empty_array()
    {
        Assert.Equal((-1, 0), BinarySearch.Find([], 1));
    }

    [Fact]
    public void Nothing_is_found_when_the_left_and_right_bounds_cross()
    {
        Assert.Equal((-1, 1), BinarySearch.Find([1, 2], 0));
    }
}

What do you think, @ErikSchierboom

2
  • Would this cause all existing solutions to fail?
  • Does this impose additional implementation details that aren’t actually required by the algorithm?
  • Does this result in the tests no longer matching the canonical data?
3

The answer to your questions is Yes for all of them. But it forces the student (user) to implement the solution the way its demanded and not using alternative approaches or builtin functions.

4

Some tracks including CoffeeScript provide a class that is array-like but also counts how many times its values are accessed. The test suite can validate the internal counter without affecting the expected function / method signature.

5

If we don’t want to change the signature of the Find function, we can add a public field that the student must take care of to pass the tests. Something like :

public static class BinarySearch
{
    public static int IterationsCount;
    public static int Find(int[] input, int value)
    {
        throw new NotImplementedException("You need to implement this function.");
    }
}

and update the tests :

public class BinarySearchTests
{
    [Fact]
    public void Finds_a_value_in_an_array_with_one_element()
    {
        Assert.Equal(0, BinarySearch.Find([6], 6));
        Assert.Equal(1, BinarySearch.IterationsCount);
    }

    [Fact]
    public void Finds_a_value_in_the_middle_of_an_array()
    {
        Assert.Equal(3, BinarySearch.Find([1, 3, 4, 6, 8, 9, 11], 6));
        Assert.Equal(1, BinarySearch.IterationsCount);
    }

    [Fact]
    public void Finds_a_value_at_the_beginning_of_an_array()
    {
        Assert.Equal(0, BinarySearch.Find([1, 3, 4, 6, 8, 9, 11], 1));
        Assert.Equal(3, BinarySearch.IterationsCount);
    }

    [Fact]
    public void Finds_a_value_at_the_end_of_an_array()
    {
        Assert.Equal(6, BinarySearch.Find([1, 3, 4, 6, 8, 9, 11], 11));
        Assert.Equal(3, BinarySearch.IterationsCount);
    }

    [Fact]
    public void Finds_a_value_in_an_array_of_odd_length()
    {
        Assert.Equal(9, BinarySearch.Find([1, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 634], 144));
        Assert.Equal(2, BinarySearch.IterationsCount);
    }

    [Fact]
    public void Finds_a_value_in_an_array_of_even_length()
    {
        Assert.Equal(5, BinarySearch.Find([1, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377], 21));
        Assert.Equal(1, BinarySearch.IterationsCount);
    }

    [Fact]
    public void Identifies_that_a_value_is_not_included_in_the_array()
    {
        Assert.Equal(-1, BinarySearch.Find([1, 3, 4, 6, 8, 9, 11], 7));
        Assert.Equal(3, BinarySearch.IterationsCount);
    }

    [Fact]
    public void A_value_smaller_than_the_array_s_smallest_value_is_not_found()
    {
        Assert.Equal(-1, BinarySearch.Find([1, 3, 4, 6, 8, 9, 11], 0));
        Assert.Equal(3, BinarySearch.IterationsCount);
    }

    [Fact]
    public void A_value_larger_than_the_array_s_largest_value_is_not_found()
    {
        Assert.Equal(-1, BinarySearch.Find([1, 3, 4, 6, 8, 9, 11], 13));
        Assert.Equal(3, BinarySearch.IterationsCount);
    }

    [Fact]
    public void Nothing_is_found_in_an_empty_array()
    {
        Assert.Equal(-1, BinarySearch.Find([], 1));
        Assert.Equal(0, BinarySearch.IterationsCount);
    }

    [Fact]
    public void Nothing_is_found_when_the_left_and_right_bounds_cross()
    {
        Assert.Equal(-1, BinarySearch.Find([1, 2], 0));
        Assert.Equal(1, BinarySearch.IterationsCount);
    }
}
6

I personally don’t think it’s necessary for us to change the exercise. If people want to cheat, that’s fine. And the proposed solutions feel a bit clunky to me, sorry

2 Likes