algorithm - Generic Binary Search in C#

Question

Below is my Generic Binary Search. It works okay with the integers type array (it finds all the elements in it). But the problem arises when I use a string array to find any string data. It runs okay for the first index and last index elements but I can't find the middle elements.

Stringarray = new string[] { "b", "a", "ab", "abc", "c" };

public static void BinarySearch<T>(T[] array, T searchFor, Comparer<T> comparer) {

        int high, low, mid;
        high = array.Length - 1;
        low = 0;
        if (array[0].Equals(searchFor))            
            Console.WriteLine("Value {0} Found At Index {1}",array[0],0);
        else if (array[high].Equals(searchFor))
            Console.WriteLine("Value {0} Found At Index {1}", array[high], high);
        else
        {
            while (low <= high)
            {
                mid = (high + low) / 2;
                if (comparer.Compare(array[mid], searchFor) == 0)
                {
                    Console.WriteLine("Value {0} Found At Index {1}", array[mid], mid);
                    break;
                }
                else
                {
                    if (comparer.Compare(searchFor, array[mid]) > 0)
                        high = mid + 1;
                    else
                        low = mid + 1;
                }

            }
            if (low > high)
            {
                Console.WriteLine("Value Not Found In the Collection");
            }
        }                 
    }

Answer 1

A binary search requires that the input be sorted. How is "b, a, ab, abc, c" sorted? It does not appear to be sorted on any obvious sort key. If you are trying to search unsorted data you should be using a hash set, not a binary search on a list.

Also, your calculation of midpoint is subtly wrong because the addition of high + low can overflow. It then becomes a negative number, which is divided by two.

This is extremely unlikely for realistically-sized arrays but it is entirely possible that you'll want to use this algorithm someday for data types that support indexing with large integers, like a memory-mapped file of sorted data.

The best practice for writing a binary search algorithm is to do (high - low) / 2 + low when calculating the midpoint, because that stays in range the whole time.