Generic binary search

Question

I have the following code for binary search

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;

namespace BinarySearch
 {
    public class IntComparer : Comparer<int>
    {
        public override int Compare(int x, int y)
        {
            if (x == y)
            {
                return 0;
            }
            else if (x > y)
            {
                return 1;
            }
            else
            {
                return -1;
            }
        }
    }

    public static class BinarySearcher
    {
        public static bool BinarySearch(this int[] array, int value)
        {
            uint bottom = 0;
            uint top = (uint)array.Length - 1;
            uint middle = top >> 1;
            while (top >= bottom)
            {
                if (array[middle] == value)
                {
                    return true;
                }
                else if (array[middle] > value)
                {
                    top = middle - 1;
                }
                else
                { 
                    bottom = middle + 1; 
                }
                middle = (bottom + top) >> 1; //to avoid overflow
            }
            return false;       
        }

        public static bool BinarySearch<T>(T item, T[] array, IComparer<T> comparer)
        {
            uint bottom = 0;
            uint top = (uint)array.Length - 1;
            uint middle = top >> 1;
            while (top >= bottom)
            {
                int compareResult = comparer.Compare(array[middle], item);

                if (compareResult == 0)
                {
                    return true;
                }
                else if (compareResult > 0)
                {
                    top = middle - 1;
                }
                else
                { 
                    bottom = middle + 1; 
                }
                middle = (bottom + top) >> 1; // middle = bottom + ((top - bottom) / 2); ?
            }
            return false;
        }

        public static bool BinarySearchRec<T>(T item, T[] array, IComparer<T> comparer)
        {
            uint bottom = 0;
            uint top = (uint)array.Length - 1;
            return BinarySearchRec<T>(item, array, comparer, bottom, top);
        }

        private static bool BinarySearchRec<T>(T item, T[] array, IComparer<T> comparer, uint bottom, uint top)
        {
            if (bottom > top)
            {
                return false;
            }
            uint middle = (bottom + top) >> 1; 
            int compareResult = comparer.Compare(array[middle], item);
            if (compareResult > 0)
            {
                return BinarySearchRec(item, array, comparer, bottom, middle - 1);
            }
            else if (compareResult < 0)
            {
                return BinarySearchRec(item, array, comparer, middle + 1, top);
            }
            else
            {
                return true;
            }
        }
    }

    class Program
    {
        private const int ITERATIONS = 1000000;

        static void Main(string[] args)
        {
            int[] sortedArray = {1,2,3,4,5,6,7,8,9,10};
            Console.WriteLine(BinarySearcher.BinarySearch<int>(10, sortedArray, new IntComparer()));

            Console.WriteLine(BinarySearcher.BinarySearchRec<int>(14, sortedArray, new IntComparer()));

            Console.WriteLine(sortedArray.BinarySearch(1));

            int[] sortedArray2 = new int[ITERATIONS];
            for (int i = 0; i < ITERATIONS; i++)
            {
                sortedArray2[i] = i;
            }

            Stopwatch stopWatch = new Stopwatch();
            stopWatch.Start();
            for (int i = 0; i < ITERATIONS; i++)
            {
                sortedArray2.BinarySearch(0);
            }
            stopWatch.Stop();
            Console.WriteLine("Time required for execution: " + stopWatch.ElapsedMilliseconds + "ms");

            stopWatch.Reset();
            stopWatch.Start();
            for (int i = 0; i < ITERATIONS; i++)
            {
                BinarySearcher.BinarySearchRec<int>(0, sortedArray2, new IntComparer());
            }
            stopWatch.Stop();
            Console.WriteLine("Time required for execution: " + stopWatch.ElapsedMilliseconds + "ms");

            stopWatch.Reset();
            stopWatch.Start();
            for (int i = 0; i < ITERATIONS; i++)
            {
                BinarySearcher.BinarySearch<int>(0, sortedArray2, new IntComparer());
            }
            stopWatch.Stop();
            Console.WriteLine("Time required for execution: " + stopWatch.ElapsedMilliseconds + "ms");

            Console.ReadLine();

        }
    }
}

I should add user input checks

What is the best way to implement public generic method for binary search? Maybe there is a better way to do so rather than with Comparer?

Answer 1

If a question of this sort pops up in a job interview, it may be a trick question, and you might actually be expected to demonstrate that you are conscious about not re-inventing the wheel. A big part of the value of .Net is that it is a very rich environment which provides programmers with lots of things already built-in and ready to use, (not to mention tested, debugged, and known to work problem-free,) so an essential skill for a .Net programmer is to know what is already there so that they do not waste time re-implementing it and debugging it.

If you can rule out the scenario of the trick question, then here is what I'd say:

1. Make your method return an int, not a bool, as the built-in binary search methods do.
2. Make an additional overload that works with System.Comparison<T> instead of System.IComparer<T>.
3. Make an additional overload that works with neither Comparison<T> nor IComparer<T>, but instead it assumes that T implements IComparable<T>.
4. Keep the middle = bottom + ((top - bottom) / 2) part, it is supposed to avoid arithmetic overflow if by any chance you are sorting an array with an incredibly large number of elements. (Not very important, but it demonstrates attention to detail.)
5. Code the public override int Compare(int x, int y) method as follows: { return x - y; } ;-)

Answer 2

The best way to implement a public generic method for binary search is by invoking the BinarySearch() method of System.Array. (Better yet, don't implement such a method at all, and call System.Array.BinarySearch() directly.)