CODEWITHSUNDEEP
listsearchloopsbinary-searchsorting
Steve Way
Steve Way

Reputation: 177

Searching a Sorted List using Binary Search (C#)

The requirement is to search an alphabetically ordered/sorted list (of string type) using a binary search method for a specified string (in the example below it is "yz") and return the results (every string that starts with the specified string and also the index of that string in the list) on a suitable control like a ListBox.

The problem is that the BinarySearch method has to run several times through a loop so that it returns all the matching strings in the list and not just one. This is my main issue. I can't figure out how to write this loop correctly. If you look inside the while loop, you'll see I'm trying to remove the result that's found from the list so it's not found and returned again. This causes the issue of the index of items in the list being changed. So it returns the wrong index for the results. For example, if you run the code below, it should return the indexes: 9, 10, 11 and 12. However, I'm getting 9, 10, 9, 10 because as the items are removed, the list becomes shorter. I could replace the resulting string with another random string instead of removing it completely, but that would mean the list is not sorted in alphabetical order anymore. For the BinarySearch method to work, the list MUST be sorted in alphabetical order.

The BinarySearch method is probably ok and doesn't need any changing. The problem is with the loop. I should mention this is for an assignment at my university so I can't use any shortcut code / built-in functions. I have tried for hours but can't figure this one out.

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

    string searchString = "yz";

    List<string> list1 = new List<string>();

    private void btnSearch_Click(object sender, RoutedEventArgs e)
    {
        if (list1.Count != 0)
        {
            list1.Clear();
        }

        list1.Add("ant");   //0
        list1.Add("bb");    //1
        list1.Add("bc");    //2 
        list1.Add("bD");    //3
        list1.Add("Be");    //4
        list1.Add("j");     //5
        list1.Add("RRR");   //6
        list1.Add("sT");    //7
        list1.Add("Uv");    //8      
        list1.Add("yz");    //9
        list1.Add("yza");   //10
        list1.Add("yzb");   //11
        list1.Add("yzc");   //12

        int index = BinarySearch(list1, 0, list1.Count, searchString);

        while (index != list1.Count)
        {
            listBox1.Items.Add("Index: " + index + " File: " + list1[index]);

            list1.RemoveAt(index); //Remove from list so we don't find it again
                                   // but this changes the index of the list

            index = BinarySearch(list1, 0, list1.Count, searchString);
        }
    }

    //BinarySearch method to search an alphabetically sorted list for a specified string
    public int BinarySearch(List<string> strList, int first, int last, string target)
    {
        int mid;    // index of the midpoint
        string midStr;  // object that is assigned listStr[mid]
        int origLast = last;
        // save original value of last
        while (first < last)
        // test for nonempty sublist
        {
            mid = (first + last) / 2;
            midStr = strList[mid];

            int indy = midStr.IndexOf(target, StringComparison.OrdinalIgnoreCase);

            if (indy == 0)
                return mid;// have a match, we're only matching the beginning of the string
            else
            {
                int order = string.Compare(target, midStr, StringComparison.OrdinalIgnoreCase);

                if (order < 0)
                    last = mid; // search lower sublist. Reset last                    
                else
                    first = mid + 1; // search upper sublist. Reset first
            }
        }
        return origLast; // target not found
    }
}

Upvotes: 2

Views: 5297

Answers (1)

Jsdodgers
Jsdodgers

Reputation: 5302

Why dont you, once you get the index of one of the elements, loop up from index until either you get to the last object or to an object that doesnt start from the string, the loop from index-1 until you get to either 0 or you reach an invalid object.

Edit: To modify your code, what I would do is after:

int index = BinarySearch(list1,0,list1.Count,searchString);

instead of doing your while loop that removes the objects, I would do:

for (int n=index;n<list1.Count;n++) {
    if (list1[n].IndexOf(searchString,StringComparison.OrdinalIgnoreCase)!=0) break;
    listBox1.Items.Add("Index: " + n + " File: " + list1[n]);
}
for (int n=index-1;n>=0;n--) {
    //Do same thing as other loop
}

This will just search both ways in the list and perform your action until it gets to an invalid string, which will then break the loop.

Upvotes: 1

Related Questions