BinarySearch() not locating items in a generic collection

When I dump the contents of a List<string>, I get…

  1. Sue
  2. Larry
  3. John Barrowman
  4. Bob

However, when I try to retrieve the index of the strings using this format…

        thisIndex = blockRetrievedList.BinarySearch("Sue");

and print the indexes in an HTML list, here’s the results that I get…

  • Using blockRetrievedList.BinarySearch(‘Larry’); : 1
  • Using blockRetrievedList.BinarySearch(‘Mike’); : -5
  • Using blockRetrievedList.BinarySearch(‘Sue’); : -5
  • Using blockRetrievedList.BinarySearch(‘Bob’); : -1
  • Using blockRetrievedList.BinarySearch(‘John Barrowman’); : -1

So while Larry comes out fine at index one, John Barrowman and Bob should be indexes 2 & 3 respectively. However, they’re coming up -1 meaning they’re not recognized as being the collection. Further Mike (who was originally in the set, but who has now been replaced by John Barrowman is coming up -5. Isn’t that supposed to be -1? And why on Earth is Sue (who is index 0, returning -5 as well?

If I retrieve the value at indexes 0-3, I do get the correct string values, but I can’t retrieve indexes. Any insights would be appreciated.

I will admit that I find myself gravitating towards dictionaries just because they offer keyed access and I like the semantics of that. Although if I just want to store information for something, there’s no reason I can’t just save that data as private fields in a custom class and then expose them as properties, correct? A dictionary / list is really intended for when you have a “collection” of the something that you needs to store: like a list to store the roles for a User class, or a dictionary if you need keyed access, but the user’s id, favorite color, prefered theme, etc. it looks more logical and better for performance to just stick each in a simple data type for storing them in the class?

It is definitely nice to see you around again. :smiley:

Yes, definitely.

Does this extend to using a database? I’ve always retrieved database records using the connected objects of ADO.NET and stuffed them into a disconnected object (DataSet or DataTable). However, now that I’m looking into generics, I found a piece of code that I think I can modify something like this…

Does this provide better performance retrieving database records, or should I download to a DataTable as I have before and just transfer the DataTable results into a Generic collection after?

CustomClass cc = new CustomClass();
SqlDataReader myReader = new SqlDataReader();
List<CustomClass> listOfRecords = new List<CustomClass();

myReader = myCommand.ExecuteReader();

     if (myReader.Read())
          cc.Id = myReader("idIntegerField");
          cc.Name = myReader("nameStringField");
          cc.DateRegistered = myReader("registeredDateTimeField");

You are about to invent LINQ to Entities. This is exactly what L2E does: Populating custom collections from a database.

If you like this idea I suggest you check L2E out before venturing down that road yourself (although it is a lot of fun).

:smiley: See there are times like this when Microsoft really “get it”. I will definitely check out L2E.

And then probably play around with it for fun too. :wink:

Thank you so much!

If you are only ever doing a single search or even a few searches, sorting the list first will eat up the advantage of a binary search.

But if the list is long-lived and you are doing multiple searches, keeping it sorted will make it more efficient in totality.

Note how the search result can be used to infer the position where to insert the element to keep it sorted.

But if you are only going to sort the list because you want to look up elements, you should look for a Dictionary/HashTable instead. They are using hashing which in general is much faster and does not require sorting.

If you do require the sorting (not just for searching), perhaps you should look at the new (.NET 4) SortedSet.

:slight_smile: Good to hear.

:frowning: Putting out resumes and taking any odd C#/PHP coding jobs or UI design work that I can get my hands on. I’ve been formally out of work for a year, and haven’t been able to find anything except 1099 work, so keep a good thought.

OK. So if your list is sorted, it’s an easy choice, run BinarySearch().

Is there any performance value to running a Sort() and then a BinarySearch() vs. running an IndexOf(), or is that exactly what IndexOf() does?

To use BinarySearch the collection must be ordered. Try sorting the list correctly (by your search criteria) before searching.

IIRC when BinarySearch returns a negative index it means that the item was not found. The value indicates where you should insert the value to preserve the ordering. IIRC you have to negate the negative value and add 1. Again, you cannot trust this index unless the list was sorted.

:slight_smile: Haven’t bumped into you in awhile. Hope you’re doing well.

Duh, cause its a binary search. OK, that makes sense. So if you want to return a simple index then IndexOf() would be the best solution, if you want to search the list for an item(s) then you’d use FindIndex(), FindLast(), or FindAll(). And if you want to perform a binary search, you’d use this. Though it sounds like binary search will take just as long unless the list is already sorted, correct?

Thx. I have been busy, but doing quite well. And you?

Actually binary search will give you wrong results if the list is not sorted. If it is sorted it will return results much faster than a simple indexof - at least when you have many items (30+) in the list.