How do I create a binary search algorithm that works with strings in an array?

Question

I'm trying to get a binary search working for strings in an array but cant seem to get it to work. This is what I have to start with. (This is for numbers but I cannot find ANY examples of a binary string search anywhere).

        private void ButtonBinary_Click(object sender, EventArgs e)
        {
            int min = 0;
            int max = arraySize - 1;
            if (!(Int32.TryParse(TextBoxSearch.Text)))
            {
                TextBoxMessage.Text = "You must enter an integer";
                return;
            }
            while (min <= max)
            {
                int mid = (min + max) / 2;
                if (target == integerArray[mid])
                {
                    TextBoxMessage.Text = target + " Found at index " + mid + 
                        ".";
                    return;
                }
                else if (integerArray[mid] >= target)
                {
                    max = mid - 1;
                }
                else
                {
                    min = mid + 1;
                }
            }
            TextBoxMessage.Text = "Not Found, try again.";
        }

Answer 1

The key component of a binary search is that you are using an ordered set of data to search through. It relies on the concept that if (for example) x > myArray[10], that this inherently means that x is bigger than myArray[0] to myArray[9] as well.

The core logic of a binary search is this:

while (/*we are looking in a non-zero-length range*/)
{
    // find the middle point of the current range
    int mid = (min + max) / 2;

    if (/* match found */)
    {
        // search concluded, we found it!
    }
    else if (/* searched value is smaller than middle point */)
    {
        // do a search in the lower half of the range
    }
    else /* searched value is larger than middle */
    {
        // do a search in the upper half of the range
    }
}

// if we get here, and the search did not conclude, then it must not have existed

Notice how none of this logic really cares what data type we're working with. The only thing that it cares about is that:

1. The array of values to search is ordered
2. The values we're working with can be compared (i.e. a < b)

So, if you want to use strings instead of ints, all you have to do is:

1. Make sure your array is ordered alphabetically

This one isn't too hard:

string[] myOrderedArray = myUnorderedArray
                              .OrderBy(x => x)
                              .ToArray();

2. Be able to find out the alphabetical order of two strings (i.e. "abc" < "bcd")

If you google "C# compare strings", you'll easily find the String.Compare method, which does exactly that.

var compareResult = String.Compare(myFirstString, mySecondString);

if(compareResult < 0)
    Console.WriteLine("Alphabetical order: myFirstString before mySecondString");
else if(compareResult > 0)
    Console.WriteLine("Alphabetical order: mySecondString before myFirstString");

Notice how very similar this is to your current if else logic.

---

@DmitryBychenko I've been specifically asked to not use Binary.Search, : ( – LaggyAu

Because I get the suspicion that this is homework, or at least a challenge that was given to you specifically for learning purposes, I have intentionally chosen to not write the code for you. I leave the composing of the above information into working code as an exercise to you.