generic binary Search in c#

Question

Below is my Generic Binary Search it works ok with the intgers 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 ok for the first index and last index elements but i cant 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

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.

Answer 2

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.

Answer 3

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

Answer 4

Hi, I send you my version of binary, search, it is based on objects, but it could be easily adapted for using generics and comparers. The code I send you also includes a method for sorting the array by means the selection algorithm. I have separated the comparison method so you can use any sort of comparison.

using System;
using System.Collections;
using System.Text;

namespace Algorithms.Test
{
    public class Program {
        static void Main(string[] args) {
            object[] x = { 4, 8, 9, 10, 5, 12, 500, 19, 222 }; object key = 10;            
            Console.WriteLine("Initial array...: {0}", x.ToCommaString() );
            x.SortBySelection();
            Console.WriteLine("Sorted array....: {0}", x.ToCommaString() );            
            Console.WriteLine("The element {0} in the sorted array is at index {1}", key, x.SearchByBinary(key));
        }
    }

    public static class Algorithms {
        public static string ToCommaString(this object[] x) {
            StringBuilder s = new StringBuilder();
            for (int i = 0; i < x.Length; i++ ) {
                s.AppendFormat("{0}{1}", x[i].ToString(), i  < x.Length - 1 ? "," : string.Empty);
            } return string.Format("[{0}]", s.ToString());
        }
        public static int SearchByBinary(this object[] x, object find) {
            int low = 0, high = x.Length - 1;
            while (low <= high) {
                int mid = (low + high) / 2, cmp = x[mid].compare(find);
                if (cmp < 0) { low = mid + 1; }
                else if (cmp > 0) { high = mid - 1; }
                else { return mid; }
            } return -(low + 1);
        }
        public static void SortBySelection(this object[] x) {
            for(int i=0; i < x.Length - 1; i++) {
                int pos = i;
                for (int j = i + 1; j < x.Length; j++) { if(x[j].compare(x[pos]) <0) { pos = j; } }
                x.swap(i, pos);                
            }
        }
        private static int compare(this object a, object b) { return Comparer.DefaultInvariant.Compare(a, b); }
        private static void swap(this object[] x, int a, int b) { object temp = x[a]; x[a] = x[b]; x[b] = temp; }
    }
}

Remember that by means of LINQ you can save a lot of effort, when working with data structures.