Click here to Skip to main content
15,868,016 members
Articles / IList
Tip/Trick

Getting the index of an item in a sorted IList

Rate me:
Please Sign up or sign in to vote.
4.56/5 (2 votes)
25 Dec 2011CPOL1 min read 35.5K   4   6
A binary search of a sorted IList to retrieve an index
Part of the code I'm working on is a sorted List<someclass>. It is sorted on a property (key) of the class, and we need to access the list to:
0) See if it contains an entry with a particular key.
1) If it does, retrieve or replace the item.
2) If not, add the item in the correct position (to keep it sorted).

What is desired is a method that will retrieve the index of the existing item or where the item ought to be. The IndexOf method of List is unsuitable for this, plus because we are assuming a sorted list, we can use a binary search in an effort to optimize the search.

Here is an implementation for the simple case where the list contains the same type as the key:

public static bool TryGetIndex<T>
(
  this System.Collections.Generic.IList<T> List
,
  T                                        Sought
,
  out int                                  Index
) where T : System.IComparable<T>
{
  bool result = false ;

  Index = 0 ;

  int lo = 0 ;
  int hi = List.Count - 1 ;

  while ( !result && ( lo <= hi ) )
  {
    Index = lo + ( hi - lo ) / 2 ;

    int diff = Sought.CompareTo ( List [ Index ] ) ;

    if (diff == 0 )
    {
      result = true ;
    }
    else if ( diff < 0 )
    {
      hi = Index - 1 ;
    }
    else
    {
      lo = ++Index ;
    }
  }

  return ( result ) ;
}


However, that is not the situation I described earlier, so I have this version:

public delegate int Comparison<T,U> ( T Op1 , U Op2 ) ;

public static bool TryGetIndex<T,U>
(
  this System.Collections.Generic.IList<U> List
,
  T                                        Sought
,
  Comparison<T,U>                          Comparer
,
  out int                                  Index
)
{
  bool result = false ;

  Index = 0 ;

  int lo = 0 ;
  int hi = List.Count - 1 ;

  while ( !result && ( lo <= hi ) )
  {
    Index = lo + ( hi - lo ) / 2 ;

    int diff = Comparer ( Sought , List [ Index ] ) ;

    if ( diff == 0 )
    {
      result = true ;
    }
    else if ( diff < 0 )
    {
      hi = Index - 1 ;
    }
    else
    {
      lo = ++Index ;
    }
  }

  return ( result ) ;
}


This requires that you provide a method to perform the comparison. Here's an example where I'm trying to find a DataRowView with a particular value for Name:

delegate
(
  string                  Op1
,
  System.Data.DataRowView Op2
)
{
  return ( System.StringComparer.InvariantCultureIgnoreCase.Compare 
  ( 
    Op1 
  , 
    Op2 [ "Name" ]  
  ) ) ;
}


Using this code to find the index of an existing item or the index where a non-existent item belongs allows you to add items where they belong to ensure that the list remains sorted. And the binary search is more efficient than a linear search, especially as the list grows large.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
United States United States
BSCS 1992 Wentworth Institute of Technology

Originally from the Boston (MA) area. Lived in SoCal for a while. Now in the Phoenix (AZ) area.

OpenVMS enthusiast, ISO 8601 evangelist, photographer, opinionated SOB, acknowledged pedant and contrarian

---------------

"I would be looking for better tekkies, too. Yours are broken." -- Paul Pedant

"Using fewer technologies is better than using more." -- Rico Mariani

"Good code is its own best documentation. As you’re about to add a comment, ask yourself, ‘How can I improve the code so that this comment isn’t needed?’" -- Steve McConnell

"Every time you write a comment, you should grimace and feel the failure of your ability of expression." -- Unknown

"If you need help knowing what to think, let me know and I'll tell you." -- Jeffrey Snover [MSFT]

"Typing is no substitute for thinking." -- R.W. Hamming

"I find it appalling that you can become a programmer with less training than it takes to become a plumber." -- Bjarne Stroustrup

ZagNut’s Law: Arrogance is inversely proportional to ability.

"Well blow me sideways with a plastic marionette. I've just learned something new - and if I could award you a 100 for that post I would. Way to go you keyboard lovegod you." -- Pete O'Hanlon

"linq'ish" sounds like "inept" in German -- Andreas Gieriet

"Things would be different if I ran the zoo." -- Dr. Seuss

"Wrong is evil, and it must be defeated." –- Jeff Ello

"A good designer must rely on experience, on precise, logical thinking, and on pedantic exactness." -- Nigel Shaw

“It’s always easier to do it the hard way.” -- Blackhart

“If Unix wasn’t so bad that you can’t give it away, Bill Gates would never have succeeded in selling Windows.” -- Blackhart

"Use vertical and horizontal whitespace generously. Generally, all binary operators except '.' and '->' should be separated from their operands by blanks."

"Omit needless local variables." -- Strunk... had he taught programming

Comments and Discussions

 
GeneralRe: Have you read the documentation for IList? Edit: Represents... Pin
PIEBALDconsult12-Jan-12 6:38
mvePIEBALDconsult12-Jan-12 6:38 
Have you read the documentation for IList?

Edit: Represents a collection of objects that can be individually accessed by index.


GeneralRe: You get list element by index, like in array, not the list. Pin
VMAtm12-Jan-12 6:16
VMAtm12-Jan-12 6:16 
GeneralReason for my vote of 1 This is not about IList - only about... Pin
VMAtm11-Jan-12 19:44
VMAtm11-Jan-12 19:44 
GeneralRe: How do you figure that? Pin
PIEBALDconsult12-Jan-12 5:26
mvePIEBALDconsult12-Jan-12 5:26 
GeneralIt may be useful to have a search method accept an IComparer... Pin
supercat99-Dec-11 12:04
supercat99-Dec-11 12:04 
GeneralRe: I expect that you could write a Comparison&lt;T,U&gt; method... Pin
PIEBALDconsult10-Dec-11 3:38
mvePIEBALDconsult10-Dec-11 3:38 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.