3
\$\begingroup\$

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Is the "write five totally unique implementations" part of kata important here? I mean, did you already write 4 others and then wrote the above but without being able to do it in simpler ways, because you had used them already? \$\endgroup\$ – harold Jun 29 at 2:54
  • \$\begingroup\$ I have added the spec I found clicking the link to the question. Make sure to do this yourself next time, because links could get stale. \$\endgroup\$ – dfhwze Jun 29 at 7:29
  • \$\begingroup\$ Another tip: there are unit tests specified when clicking the link. You could incorporate them in the question so we can easely verify your algorithm. \$\endgroup\$ – dfhwze Jun 29 at 7:32
3
\$\begingroup\$

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();
}
\$\endgroup\$
  • \$\begingroup\$ Why did you write subject = subject ?? instead of the simpler if (subject == null)? \$\endgroup\$ – Roland Illig Jun 29 at 10:54
  • 2
    \$\begingroup\$ @RolandIllig I don't like an if without parentheses, unless the statement within is very short and I don't like a full-on if block if I can avoid it. This is a typical scenario where I would go with the null-coalescing operator. \$\endgroup\$ – dfhwze Jun 29 at 12:47
  • \$\begingroup\$ @RolandIllig mhmm, a matter of taste... I find the new exception expression ?? throw ... that is used here is simpler. \$\endgroup\$ – t3chb0t Jun 29 at 14:55
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ The value <= subject[mid] is confusing since the two expressions can never be equal. Therefore value < subject[mid] is preferrable. \$\endgroup\$ – Roland Illig Jun 29 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.