Binary search for List<object>

Question

Hello I need some help in my library. I'm trying to implement a binary search from my List<> but its not working so well.

This is my Library class.

    private class Library
{
    List<object> library = new List<object>();

    public void AddBook(string bookName, string bookAuthor, int bookIDNum)
    {
        //Add books to the library.
        string bookEntry = bookName + " " + bookAuthor + " " + bookIDNum;
        library.Add(bookEntry);
        library.TrimExcess();
    }

        public void SearchLibrary(string bookName)
    {
        //Searches the library by title
        library.Sort();
        int low = 0;
        int high = library.Count;
        int mid = 0;
        int steps = 0;
        while(!bookName)
        {
            steps++;
            mid = (low + high)/2;
            if(bookName == library[mid])
            {
                return true;
            }
            else if(bookName < library[mid])
            {
                high = mid;
            }
            else
            {
                low = mid;
            }
            if(low > high-1 || high < low+1)
            {
                return false;
            }
        }
    }
}
}

If there's a better way I can make a search method I would appreciate it, thank you.

Answer 1

Without commenting on the details of your algorithm, there are some issues with your code. You could've found all these issues by looking at the compiler's error messages.

• You return true and false, yet your method specifies it returns void. Change that to bool instead.

  public bool SearchLibrary(string bookName)
  

• You do !bookName, where I presume you want to check whether it is null or not. You must do that explicitly in C#.

  while (bookName != null)
  

• You compare two strings, but the < operator is not overloaded for strings. Use CompareTo instead:

  else if (bookName.CompareTo(library[mid]) < 0)
  

• Not all code paths return a value. You'll have to return a value no matter what execution path it takes. For example, end your method with this:

  return false;
  

Then there is an issue with your algorithm: it will run forever when there is no match. As I suspect this may be homework, I'll leave it an an exercise for the OP to solve this issue.

---

And if this isn't a homework exercise, you could've saved yourself some trouble:

The List<T> class has a method BinarySearch that uses the default comparer to compare the objects in the list.

library.Sort();
bool found = (library.BinarySearch(bookName) >= 0);