Last Update:

# Code Kata - chop

Table of Contents

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

I've prepared a valuable bonus if you're interested in Modern C++!

Learn all major features of recent C++ Standards!

Check it out here:

I've recently released a new book on Modern C++: C++ Initialization Story @Leanpub~210 pages, ~70 code samples, 2 quizzes, and several exercises. All for Modern C++ techniques related to initialization in C++20. |