Why doesn't IList have a BinarySearch method

Why doesn't IList have a BinarySearch method

• Shahar Prish - MSFT

  Sorting a list isn't always a necessary or useful operation (as opposed to, say, adding, removing, or accessing elements). If BinarySearch were a part of the IList<T> interface, any type deriving from IList<T> would be force to implement it, even if it made no sense. List<T>, on the other hand, is a concrete type and free to include additional functionality beyond the requirements of the interface.

  A SortedList<K, V>, on the other hand, is always sorted by the provided key. The BinarySearch functionality is provided by the indexer, which guarantees retrieval in O(log n) time.

  -Tom Meschter
  Software Dev, Visual C# IDE

  
  
  

• crystalamber

  I think what Tom meant was that you can implement your own BinarySearch by using SortedList's Indexer. As to why SortedList doesn't already have it, I guess they didn't see the need for both IndexOfKey and BinarySearch, since they do almost the same thing. They chose IndexOfKey because its consistent with the design of similar classes, and it probably the more commonly used. Unfortunately, that means people like you will have to implement their own. It seems that MS left a lot of things out of the Collections classes to maintain simplicity.
  

• 4r09384r3l4kn

  I perhaps should have been more exact in my language. I meant that the SortedList<key, value> indexer (SortedList<key, value>[key], as you correctly state) provides somewhat similar functionality to List<T>.BinarySearch(), in terms of them both performing a lookup and doing it in O(log n) time. They are not directly comparable given that List<T>.BinarySearch() takes a value and returns an index whereas the SortedList<K, V> indexer takes a key and returns a value (if any). I drew attention to the SortedList<K, V> indexer in hopes that it would provide the functionality MuscleHead is looking for, not to suggest that it was strictly equivalent to List<T>.BinarySearch().

  I would say the lack of a BinarySearch method on SortedList<K, V> is an inconsistency in design rather than a bug. Ultimately SortedList<K, V> works the way it is supposed to. It doesn't work the way List<T> does when it comes to sorting and/or searching, but then it never claims to.

  All this is rather academic, though. Perhaps you could provide more information about the code you're trying to write, so that we can help you find a proper solution For instance, even though you've mentioned SortedList<K, V>, it isn't clear to me if you actually care about the values or if the keys are the main thing.

  -Tom Meschter
  Software Dev, Visual C# IDE

  
  
  

• ArizonaJoe

  Nimrand,

  Hmm, I don't think that's what Tom meant. He says "The BinarySearch functionality is provided by the indexer, which guarantees retrieval in O(log n) time." By indexer Tom means SortedList<key, value>[key], which is useless for implementing a Binary Search.

  My work around of casting (SortedList<key, value>.Keys as List<key>) didn't work. It really does seem like a bug that SortedList doesn't have Binary Search functionality that works the same as Array.BinarySearch() when the key sought is not in the list.

  Copying all the keys from the list into an array (as I think Peca55 suggests) doesn't make much sense in this case. I need to do this search repeatedly.

  
  
  

• Fei-tian

  Nimrand,

  SortedList.IndexOfKey() *could* be what I'm looking for (I think that's actually a better name than BinarySearch(), although it's awkward that it be name IndexOfKey in SortedList and BinarySearch in List and Array classes). Unfortunately, if the key doesn't exist in the list, then IndexOfKey() returns -1, instead of the "negated" index value of the next largest element. This latter behavior is needed in my case because my keys are dates, and if a date doesn't exist, I want the "previous" valid date.

  Thanks for your answer though.

  
  
  

• sudarsan

  Hi Tom,

  Your explanation of why IList<> doesn't define a BinarySearch() method is reasonable.

  However, your 2nd point about the indexer providing BinarySearch() isn't useful (in my case) when the SortedList doesn't contain an item. In my program, the keys are DateTime's; if my SortedList doesn't contain a DateTime, then I would want to know the (negated) index of the next largest DateTime (just like BinarySearch() does for arrays and Lists). This doesn't work with the indexer.

  Thanks for your answer.

  
  
  

• StuartGM

  My guess would be because it's just an interface, you have to make the methods ect. ur self
  

• Tomay

  Peek the following blog: C# object arrays BinarySearch, Sort and IComparer It should be partial solution to your problem.

  
  
  

• Lockhouse

  The IndexOfKey method of SortedList<> is implemented with a BinarySearch. Is that what you're looking for
  

• bjquinniii

  Nimrand,

  Hmm, I don't think that's what Tom meant. He says "The BinarySearch functionality is provided by the indexer, which guarantees retrieval in O(log n) time." By indexer Tom means SortedList<key, value>[key], which is useless for implementing a Binary Search.

  My work around of casting (SortedList<key, value>.Keys as List<key>) didn't work. It really does seem like a bug that SortedList doesn't have Binary Search functionality that works the same as Array.BinarySearch() when the key sought is not in the list.

  Copying all the keys from the list into an array (as I think Peca55 suggests) doesn't make much sense in this case. I need to do this search repeatedly.

  
  
  
• Why doesn't IList have a BinarySearch method