2
\$\begingroup\$

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?

\$\endgroup\$
4
  • \$\begingroup\$ In C# both the System.Generic.List class and the System.Array class already have generic BinarySearch() methods which work with Comparer delegates, or with objects implementing IComparable. They are known to work very well, and they perform actual search, meaning that they return the index of the item found, (or, if not found, the negated index at which it should be inserted,) instead of what your methods do, which is to simply answer the question of whether an item exists in an array. So, why are you trying to re-invent this wheel? \$\endgroup\$ – Mike Nakis Nov 28 '11 at 10:26
  • \$\begingroup\$ prepering for an interview \$\endgroup\$ – Lukasz Madon Nov 28 '11 at 12:14
  • \$\begingroup\$ So, how did your interview go, @lukas? \$\endgroup\$ – Mike Nakis Dec 6 '11 at 11:46
  • \$\begingroup\$ rescheduled :P ... \$\endgroup\$ – Lukasz Madon Dec 6 '11 at 12:14
1
\$\begingroup\$

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; } ;-)
\$\endgroup\$
0
\$\begingroup\$

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.)

\$\endgroup\$

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.