Binary search of strings in an array in C#

Question

Ok so I have been at this same error for about 18 hours and am totally lost. What I am trying to do is conduct a binary search where the search begins in the middle of the array and then eliminates half of the array everytime by comparing the term that was searched for to the middle term. So far my code is not producing errors except when I try to compare if the searched term is greater than the middle term. I know that I am trying to compare two strings and so greater than doesn't apply, but I have no idea how else to do it. Here is my code:

public partial class MainWindow : Window
{
    public MainWindow()
    {
        InitializeComponent();
    }

    string[] contacts = new string[20];

    private void button1_Click(object sender, RoutedEventArgs e)
    {
        listBox1.Items.Clear(); //Clears the ListBox of all previous items

        if (!File.Exists("Week3List.txt")) //Verifies that the file exists
        {
            MessageBox.Show("You need to write the file first", "Validation", MessageBoxButton.OK); //Notifies the user if the file does not exist
            return;
        }
        using (StreamReader sr = new StreamReader("Week3List.txt")) //Designates the path to the file that was created
        {
            try
            {
                contacts = File.ReadAllLines("Week3List.txt");
                Array.Sort(contacts);
                foreach (string contact in contacts)
                {
                    listBox1.Items.Add(contact);
                }
                sr.Close(); //Closes the StreamReader
            }
            catch (Exception ex) //A catch to handle access errors
            {
                MessageBox.Show(ex.ToString(), "Exception Handler", MessageBoxButton.OK); //Adds the error message to the ListBox
            }
        }
    }

    private void button2_Click(object sender, RoutedEventArgs e)
    {
        bSearch(contacts);
    }

    private void bSearch(string[] contacts)
    {
        int index = Array.BinarySearch(contacts, textBox1.Text);
    }

    public int BinarySearch(string[] contacts, string searchTerm)
    {
        int first = 0;
        int last = contacts.Length - 1;
        int position = -1;
        bool found = false;
        int compCount = 0;
        searchTerm = textBox1.Text;

        while (found != true && first <= last)
        {
            int middle = (first + last) / 2;

            if (contacts[middle] == searchTerm)
            {
                found = true;
                position = middle;
                compCount++;

                MessageBox.Show("Your search has been found after " + compCount + "comparisons.");
            }
            else if (contacts[middle] > searchTerm)
            {
                last = middle;
                compCount++;
            }
            else
            {
                first = middle;
                compCount++;
            }
        }
        return position;
        return compCount;
    }
}
}

Does anyone see where I am going wrong or know of a way to compare the two for a greater or less than value? I thought because it was sorted that it might compare the first letter and determine based off of that but I was wrong.

Are you doing a binary search on 20 items? Or is this just an example and the number of items is far far larger? — Enigmativity
– Enigmativity, Commented Sep 30, 2014 at 5:12
The binary search is of 20 names read from a text file. As far as the 2 return instruction continuously comment I am not sure what you mean. Did I call a continuous return that I missed? — Cameron Briggs
– Cameron Briggs, Commented Sep 30, 2014 at 5:27

Ofiris · Accepted Answer · 2014-09-30 05:16:35Z

5

Just use the List<T>.BinarySearch method.

List<String> myList = new List<String>{"Apple", "Microsoft", "Yahoo", "StackOverflow" };
myList.Sort(); //Apple Microsoft StackOverflow Yahoo 
myList.BinarySearch("Yahoo"); // 3

Or if using Array:

string[] myArr = new string[]{"Apple", "Microsoft", "Yahoo", "StackOverflow" };
Array.Sort(myArr); //Apple Microsoft StackOverflow Yahoo 
Array.BinarySearch<string>(myArr, "Yahoo"); // 3

answered Sep 30, 2014 at 5:16

Ofiris

6,1716 gold badges38 silver badges59 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Jon Over a year ago

I doubt that's in the spirit of the homework exercise :)

Cameron Briggs · Accepted Answer · 2014-09-30 06:19:44Z

1

Alright thank you to RegularExpression for the suggestion to look at a method for comparing strings. I changed the code

if (contacts[middle] == searchTerm) and else if (contacts[middle] > searchTerm)

to

if (string.Compare(contacts[middle], searchTerm, true) == 0) and else if (string.Compare(contacts[middle], searchTerm, true) > 0)

and it is now working perfectly! Thank you all for the quick responses.

answered Sep 30, 2014 at 6:19

Cameron Briggs

711 gold badge1 silver badge8 bronze badges

Comments

RegularExpression · Accepted Answer · 2014-09-30 05:39:36Z

0

Look at this method for comparing strings. It will tell you whether a string is greater, less, or equal (in value) to another string:

http://msdn.microsoft.com/en-us/library/zkcaxw5y%28v=vs.110%29.aspx

answered Sep 30, 2014 at 5:39

RegularExpression

3,5512 gold badges27 silver badges36 bronze badges

1 Comment

Mehdi Khademloo Over a year ago

is this not a comment??

Margus · Accepted Answer · 2014-09-30 05:15:49Z

0

Well, have you tried :

contacts.ToList().BinarySearch(searchTerm);

answered Sep 30, 2014 at 5:15

Margus

20.1k15 gold badges59 silver badges104 bronze badges

1 Comment

Cameron Briggs Over a year ago

I thought about something like that but I have to have a counter for the number of comparisons made. That means I had to write the BinarySearch itself instead of using the auto generated one. (I think that is what you are suggesting) My issue is that in the BinarySearch method the else if comparison doesn't work because they are strings. Would converting it to a list instead of an Array help with that? I am still very new to C#.

Rezo Megrelidze · Accepted Answer · 2014-09-30 06:35:57Z

0

If you want to do a binary search on a string array this is the way to do it. You may want to choose a different Culture for the StringComparer.

string[] arr = {"a","b","c","d","e","f","g"};

int k = Array.BinarySearch(arr,"d",StringComparer.InvariantCulture);

answered Sep 30, 2014 at 6:35

Rezo Megrelidze

3,0801 gold badge28 silver badges30 bronze badges

Comments

Ali Besharati · Accepted Answer · 2022-01-20 16:06:29Z

If you want to solve this problem without using built-in Extension and Helper of programming language You Should do this : ( See the online demo)

important: Your Array should be sorted because the Binarry-Search is not working on the UnSorted list.

 static int Find(string[] data, string SearachItem)
    {
        //It is mandatory to turn off case-sensitive by convert values to lowercase or uppercase
        ConvertArrayToLower(data); 
        string Lower = SearachItem.ToLower();
        
        //initiate
        char XChar = Lower[0]; // we will compare first char of Search Item by first char of array values
        int FirstIndex = 0;
        int LastIndex = data.Length - 1;
        while (FirstIndex <= LastIndex)
        {
            int MiddelIndex = (FirstIndex + LastIndex) / 2;
            char middel = data[MiddelIndex][0];
            if (XChar > middel)
                FirstIndex = MiddelIndex + 1;
            else if (XChar < middel)
                LastIndex = MiddelIndex - 1;
            else if (data[MiddelIndex] != Lower) // maybe the first char of two or more values will be the same so we should go to the next step
            {
                FirstIndex = MiddelIndex + 1;

            }
            else return MiddelIndex; // if found
        }

        //if not found
        return -1;
    }

    private static void ConvertArrayToLower(string[] data)
    {

        for (int i = 0; i < data.Length; i++)
        {
            data[i] = data[i].ToLower();
        }
    }

See the online demo

Collectives™ on Stack Overflow

Binary search of strings in an array in C#

6 Answers 6

1 Comment

Comments

1 Comment

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

1 Comment

Comments

1 Comment

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related