Generic Binary Search in C#

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;
   开发者_Python百科     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");
            }
        }                 
    }

---

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.

---

The two lines are suspect:

high = mid + 1
low = mid + 1

Hmm. Look at the offsets. Of course this is well documented Binary Search Algorithm on Wikipedia. You also do extra work. Examine the pseudo-code and examples closely.

---

pst Your advice really worked. :) this code is working for both int and string.

    public static int BinarySearch<T>(T[] array, T searchFor, Comparer<T> comparer)
    {
        int high, low, mid;
        high = array.Length - 1;
        low = 0;
        if (array[0].Equals(searchFor))
            return 0;
        else if (array[high].Equals(searchFor))
            return high;
        else
        {
            while (low <= high)
            {                   
                mid = (high + low) / 2;
                if (comparer.Compare(array[mid], searchFor) == 0)                   
                    return mid;                    
                else if (comparer.Compare(array[mid], searchFor) > 0)                    
                    high = mid - 1;                    
                else                    
                    low = mid + 1;                  
            }
            return -1;                
        }                 
    }

---

//Binary search recursive method

    public void BinarySearch(int[] input,int key,int start,int end)
    {
        int index=-1;
        int mid=(start+end)/2;
        if (input[start] <= key && key <= input[end])
        {
            if (key < input[mid])
                BinarySearch(input, key, start, mid);
            else if (key > input[mid])
                BinarySearch(input, key, mid + 1, end);
            else if (key == input[mid])
                index = mid;
            if (index != -1)
                Console.WriteLine("got it at " + index);
        }
    }  

     int[] input4 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };   
     BinarySearch(input4, 1, 0, 8);