codekata: Binary search on an int array

Question

I'm following Karate Chop kata for a binary search. I really wanted to avoid built in functionality within the language. I'm pretty new to C# so any recommendations is greatly appreciated.

Spec: Binary chop on an int array to find the index.

A binary chop (sometimes called the more prosaic binary search) finds the position of value in a sorted array of values. It achieves some efficiency by halving the number of items under consideration each time it probes the values: in the first pass it determines whether the required value is in the top or the bottom half of the list of values. In the second pass in considers only this half, again dividing it in to two. It stops when it finds the value it is looking for, or when it runs out of array to search. Binary searches are a favorite of CS lecturers.

http://codekata.com/kata/kata02-karate-chop/

public static int Chop(int val, int[] subject)
{
    // if the array count is odd
    if (subject.Length % 2 != 0)
    {
        // if the last index is the value, we're done
        if (subject[subject.Length - 1] == val)
        {
            return subject.Length - 1;
        }
        // remove the last index so that the array length is even
        subject = new ArraySegment<int>(subject, 0, subject.Length - 1).ToArray();
    }
    // get the mid point
    var mid = subject.Length / 2;
    if (mid > 4)
    {
        int[] chopped = new int[mid];
        Array.Copy(subject, chopped, mid);
        if (chopped[chopped.Length - 1] > val)
        {
            Chop(val, chopped);
        }
        else
        {
            var segment = new ArraySegment<int>(subject, mid, subject.Length - mid);
            Chop(val, segment.ToArray());
        }
    }
    int index = -1;

    for (int j = 0; j < subject.Length; j++)
    {
        if (val == subject[j])
        {
            if (index != -1)
            {
                duplicateIndexes.Add(index);
                duplicateIndexes.Add(j);
            }
            index = j;
        }
    }
    return index;
}

Answer 1

Review

• You make a special branch to distinguish odd from even array lengths. if (subject.Length % 2 != 0) This is not required because getting the mid of an array can just be retrieved as (end - start) / 2. In case of an even array, you get the left index of the mid index pair. This is not a bad thing, we are not calculating a median here.
• You write alot of comments // if the array count is odd. Because you are a beginner, this is ok. But try writing code in a way these obvious comments are not required. Pick good method and variable names.
• You have taken the chopping part a bit literally. Array.Copy(subject, chopped, mid); is an expensive operation. Perhaps you could have worked on the source array, but played around with the start and end index instead.

Alternative

Use an algorithm that keeps refining start and end index until a match is found. This way, you don't need to make new array segments. This works for both odd and even arrays.

public static int Chop(int value, int[] subject)
{
    subject = subject ?? throw new ArgumentNullException(nameof(subject));
    if (subject.Length == 0) return -1;
    var start = 0;
    var end = subject.Length - 1;
    return Chop(value, subject, start, end);
}

private static int Chop(int value, int[] subject, int start, int end)
{
    var span = end - start;
    var mid = start + span / 2

    if (subject[mid] == value) return mid;
    if (span == 0)  return -1; 

    if (subject[mid] > value)
    {
        return Chop(value, subject, start, mid);
    }

    return Chop(value, subject, mid + 1, end);
}

Test

static void Main(string[] args)
{
    Console.WriteLine(Chop(3, new[] { 2 }));
    Console.WriteLine(Chop(3, new[] { 3 }));
    Console.WriteLine(Chop(3, new[] { 3, 4 }));
    Console.WriteLine(Chop(3, new[] { -1, 3, 4 }));
    Console.WriteLine(Chop(3, new[] { 1, 2, 3, 4 }));
    Console.WriteLine(Chop(3, new int[0]));
    Console.ReadKey();
}

Answer 2

dfhwze has said the most, I just miss the point of:

      duplicateIndexes.Add(index);
        duplicateIndexes.Add(j);

---

Recursion is an important pattern when programming, and sometimes it is inevitably, but in most circumstances you can find an iterative solution for the same problem. The advantages with iterative solutions are that they often are easier to understand and debug, and they are mostly also more time efficient - unless the language supports tail call optimization (C# doesn't AFAIK) (and your recursive call is a tail call), and they of course never overflow the stack.

A binary search can easily be implemented iteratively:

public int Chop(int value, int[] subject)
{
  subject = subject ?? throw new ArgumentNullException(nameof(subject));
  if (subject.Length == 0 || value < subject[0] || value > subject[subject.Length - 1]) return -1;

  int start = 0;
  int end = subject.Length - 1;

  while (start <= end)
  {
    int mid = start + (end - start) / 2;

    if (value == subject[mid])
      return mid;
    if (value < subject[mid])
      end = mid;
    else
      start = mid + 1;
  }

  return -1;
}