Code Kata - chop

As it appears, our ability to code can be improved by taking some practices from martial arts! CodeKata is a catchy name for set of exercises that done regularly should make your coding skills better. Today I would like to share my “answers” to one of the Kata - karate chop, or simply the binary search algorithm.

The Problem  

Input: sorted array, target value to search

Output: index in the array where the target value is positioned or -1 if not

Additional info: implement in 5 different ways using language of your choice.

UnitTests

int[] values = { 0, 1, 2, 3, 4, 5 };
Assert.AreEqual(0, chopMethod(0, values));
Assert.AreEqual(1, chopMethod(1, values));
Assert.AreEqual(2, chopMethod(2, values));
Assert.AreEqual(3, chopMethod(3, values));
Assert.AreEqual(-1, chopMethod(6, values));
Assert.AreEqual(-1, chopMethod(1, null));
Assert.AreEqual(-1, chopMethod(1, new int[]{}));

The Solution(s)  

1. Simple loop version

public static int chop(int target, int[] values)
{
    if (values == null)
        return -1;
            
    int left = 0;
    int right = values.Length - 1;

    while (left <= right)
    {
        int center = (left + right)/2;

        if (target == values[center])
            return center;

        if (target < values[center])
        {
            right = center - 1;
        }
        else
        {
            left = center + 1;
        }
    }

    return -1;
}

As you see I choose C# for doing this task. The first version is quite easy but I needed some time to recall how binary search actually works :)

2. Recursion

public static int chop2(int target, int[] values)
{
    if (values == null || values.Length == 0) 
        return -1;

    return chopRecursive(target, values, 0, values.Length-1);
}

private static int chopRecursive(int target, int[] values, int left, int right)
{
    if (left > right)
        return -1;

    int center = (left + right) / 2;

    if (target == values[center])
        return center;

    if (target < values[center])
        return chopRecursive(target, values, left, center-1);
            
    return chopRecursive(target, values, center+1, right);
}

3. Array slicing

public static int chopSlice(int target, int[] values)
{
    if (values == null)
        return -1;

    return chopSliceSegment(target, new ArraySegment(values));
}

private static int chopSliceSegment(int target, ArraySegment valueSegment)
{
    if (valueSegment.Count == 0) 
        return -1;

    int left = valueSegment.Offset;
    int right = valueSegment.Offset + valueSegment.Count - 1;
    int center = (left + right) / 2;
            
    if (target == valueSegment.Array[center])
        return center;

    if (target < valueSegment.Array[center])
        return chopSliceSegment(target, new ArraySegment<int>(valueSegment.Array, left, center - left));
                
    return chopSliceSegment(target, new ArraySegment<int>(valueSegment.Array, center + 1, right - center));
}

4. Array slicing with copy

public static int chopSlice2(int target, int[] values)
{
    if (values == null || values.Length == 0)
        return -1;

    int left = 0;
    int right = values.Length - 1;
    int center = (left + right) / 2;

    if (target == values[center])
        return center;

    if (target < values[center])
        return chopSlice2(target, SubArray(values, 0, center-1));

    int ret = chopSlice2(target, SubArray(values, center+1, right));
    return ret == -1 ? ret : center + 1 + ret;
}

private static T[] SubArray<T>(T[] data, int left, int right)
{
    T[] result = new T[right - left + 1];
    Array.Copy(data, left, result, 0, result.Length);
    return result;
}

After three first version it was quite hard to came up with some new idea…

5. Generics

public static int chopGeneric<T>(T target, T[] values) 
    where T : System.IComparable<T>
{
    if (values == null)
        return -1;

    int left = 0;
    int right = values.Length - 1;

    while (left <= right)
    {
        int center = (left + right) / 2;
        int cmp = target.CompareTo(values[center]);

        if (cmp == 0) return center;
        else if (cmp < 0) right = center - 1;
        else left = center + 1;
    }

    return -1;
}

The last version is not that impressive, but I could not find any other solution.

Conclusion  

• First version took more time (I did it not in one day but in two). First, you have to set up development environment, write unit test and prepare the project. Then figure out the algorithm… and write the solution.
• I set some time limit: like 20… 30 minutes each day, so instead of reading IT news in the morning I spent the time thinking and practising. This is very good exercise and easily can become a good habit!
• Time limit forces you to work a bit faster.
• I was able to recall my C# knowledge fast. It is great when you have some specific task to do.
• All in all this exercise was very interesting and I advise to try it out.
• Now I prepare for the next Kata :) Of course it will be in a different language.

Link to the repository: github.com/fenbf/codekata/chop

Title image comes from commons.wikimedia.org