c# binary search strings from array (including json)

Question

So I have a Json implimentation that reads characters, the names go into arrays then I use Array.BinarySearch to get the position of the element.

I'm researching how to impliment the Binary Search own my own. I'm having trouble seeing logically what to do with the string name that is entered for the search.

Instead of using Array.BinarySearch, I need a separate method with the algorithm.

Any advice / strategy? :)

example:

       /* json array implimented, manu printed etc... before this point,      */ 



   static void FindCharacters(Characters[] characters)
    {
        Characters result = new Characters();

        string userInput = Console.ReadLine();

        string[] name = new string[10000];



        Console.Write("Search Name : ");
        string searchKeyword = Console.ReadLine();

        if (userInput.ToLower() == "name")
        {

            name = characters.Select(m => m.Name).ToArray();   

        Array.Sort(name);
        Sorting.Sort(characters, searchKeyword);


        var tmp = BinarySearch(name, searchKeyword); 

        if (tmp < 0)
        {
            Console.WriteLine("No data found!");
            return;
        }
        else
        {
            result = characters[tmp];

            CharacterPrint(result);
        }
            //result = characters[tmp];  //Convert.ToInt32(tmp)
            //CharacterPrint(result);

}

    public static int BinarySearch(int[] name, int item)
    {

        int min = 0;
        int N = name.Length;
        int max = N - 1;
        do
        {
            int mid = (min + max) / 2;
            if (item > name[mid])
                min = mid + 1;
            else
                max = mid - 1;
            if (name[mid] == item)
                return mid;
            //if (min > max)
            //   break;
        } while (min <= max);
        return -1;
    }

Answer 1

Your int solution will work perfectly fine for strings. In fact, by just tweaking a couple lines, it would work for any data type that implements IComparable:

public static int BinarySearch<T>(T[] name, T item) 
    where T : IComparable<T>
{

    int min = 0;
    int N = name.Length;
    int max = N - 1;
    do
    {
        int mid = (min + max) / 2;
        int t = item.CompareTo(name[mid]);      // Temp value holder
        if (t > 0)                              // item > name[mid]
            min = mid + 1;
        else if (t < 0)                         // item < name[mid]
            max = mid - 1;
        else                                    // item == name[mid]
            return mid;
        //if (min > max)
        //   break;
    } while (min <= max);
    return -1;
}

You can call it like this:

string[] names = // ...
string name = //...

// Explicit calling
int idx = BinarySearch<string>(names, name);

// Implicit calling
// The following option works because the C# compiler can tell you are
// using two values of type string and inserts the correct generic
// type for you
int idx = BinarySearch(names, name);

You can see the changes made above reflect how to replace the default comparison operators (i.e. "<", ">", "==") with their CompareTo equivolents. The extra variable t is there to avoid redundantly calling CompareTo on the objects twice.

The way that CompareTo works is that it takes the calling object and compares it with the passed object. If the passed object would appear before the calling object in a sorted list, the method returns -1. If it would appear after, it returns 1. If they are the same, it returns 0.

See the following example for an illustration of this:

// The following values are compared based on standard lexical alphabetical order

a.CompareTo(b); // "b" would appear after "a", so this returns 1
c.CompareTo(b); // "b" would appear before "c", so this returns -1
b.CompareTo(b); // "b" and "b" are the same value, so this returns 0