# Generic binary search

I have the following code for binary search

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
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");

}
}
}


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?

• 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? Nov 28 '11 at 10:26
• prepering for an interview Nov 28 '11 at 12:14
• So, how did your interview go, @lukas? Dec 6 '11 at 11:46
• rescheduled :P ... Dec 6 '11 at 12:14

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