codekata: Binary search on an int array 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&lt;int&gt;(subject, 0, subject.Length - 1).ToArray();
    }
    // get the mid point
    var mid = subject.Length / 2;
    if (mid &gt; 4)
    {
        int[] chopped = new int[mid];
        Array.Copy(subject, chopped, mid);
        if (chopped[chopped.Length - 1] &gt; val)
        {
            Chop(val, chopped);
        }
        else
        {
            var segment = new ArraySegment&lt;int&gt;(subject, mid, subject.Length - mid);
            Chop(val, segment.ToArray());
        }
    }
    int index = -1;

    for (int j = 0; j &lt; subject.Length; j++)
    {
        if (val == subject[j])
        {
            if (index != -1)
            {
                duplicateIndexes.Add(index);
                duplicateIndexes.Add(j);
            }
            index = j;
        }
    }
    return index;
}
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] &gt; 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();
}