SortedList, searching for items efficiently
Author Message
SortedList, searching for items efficiently

Greetings,

I have a list of sorted items. For the sake of simplicity, let's say
that these items are of type 'int' and are stored in a SortedList. The list
contains about 10,000 ints. Now, what is the fastest way for me to find the
index of the *first* item in the list that is greater than or equal to
5,654?  What is the fastest way for me to find the *latest* index
corresponding to a value less than or equal to 3,331?

Right now I'm handling this the "brute" force way. I'm simply iterating
through the entire list and examining each item. Since the items are sorted,
it seems that there should be a more efficient way. None of the SortedList
methods seem to be what I'm looking for.

--
If you need to reach me by email, use dsworde1 AT san DOT rr DOT com

David

Wed, 30 Mar 2005 04:43:45 GMT
SortedList, searching for items efficiently
I don't think there are any standard .NET functions to do what you're asking
for, so you'd have to write the code yourself.

The more "general purpose" approach would be to just do a binary search.  If
you have 10,000 ints, take the middle one at position 5000 and test it.  If
it's higher than the number you want, then look at the first 5000 numbers.
If it's lower than the number you want, look at the second 5000.  Then
repeat the process on that set.  ie, the next number you look at would be
#2500 or #7500 depending on the result of your test on #5000

You have the additional requirement that you want to find the first or last
occurance of that number.  To do that when you find the number you want, you
need to do additional searches until you identify the exact boundary of two
consecutive entries where one is the number that you want, and the other is
too small (if you're looking for the first) or too large (if you're looking
for the last).  Then you'll know you've found the "first" entry.

Wyatt

"David Sworder (formerly known as "Rev. Dr. Hulio Manuel Sanchez-Cruz")"

Quote:

> Greetings,

>     I have a list of sorted items. For the sake of simplicity, let's say
> that these items are of type 'int' and are stored in a SortedList. The
list
> contains about 10,000 ints. Now, what is the fastest way for me to find
the
> index of the *first* item in the list that is greater than or equal to
> 5,654?  What is the fastest way for me to find the *latest* index
> corresponding to a value less than or equal to 3,331?

>     Right now I'm handling this the "brute" force way. I'm simply
iterating
> through the entire list and examining each item. Since the items are
sorted,
> it seems that there should be a more efficient way. None of the SortedList
> methods seem to be what I'm looking for.

> --
> If you need to reach me by email, use dsworde1 AT san DOT rr DOT com

> David

Wed, 30 Mar 2005 05:00:16 GMT
SortedList, searching for items efficiently

Quote:
> I don't think there are any standard .NET functions to do what you're
> for, so you'd have to write the code yourself.

Hi Wyatt... I was considering taking the approach that you described,
but I was hoping that the .NET framework had already done the work for me.
:(

David

Wed, 30 Mar 2005 05:07:09 GMT
SortedList, searching for items efficiently
Actually, there is a method called Array.BinarySearch() which is pretty
close to what I'm looking for.

Wed, 30 Mar 2005 05:20:35 GMT
SortedList, searching for items efficiently
I don't think you can use BinarySearch() because of your requirement that
you want to find the first or the last instance, whereas BinarySearch as it
is now will only let you find "an" instance.

For a moment I thought you could write an IComparer that took into account
an element's neighbours when doing a comparison, but that's not directly
possible because the IComparer.Compare function only takes the 2 values and
doesn't pass in the indexes that those elements are at.

"David Sworder (formerly known as "Rev. Dr. Hulio Manuel Sanchez-Cruz")"

Quote:

>     Actually, there is a method called Array.BinarySearch() which is
pretty
> close to what I'm looking for.

Wed, 30 Mar 2005 05:54:39 GMT
SortedList, searching for items efficiently

Quote:
> I don't think you can use BinarySearch() because of your requirement that
> you want to find the first or the last instance, whereas BinarySearch as
it
> is now will only let you find "an" instance.

Yeah, this is true. However, BinarySearch() gives me a decent starting
point to begin searching for the appropriate record. It's much faster than
my "brute force" method of examining each and every item in the list.

Thanks for the tip. Had you not mentioned the concept of a "binary
search", I never would have thought to look for a BinarySearch() method.

David

Wed, 30 Mar 2005 07:07:20 GMT
SortedList, searching for items efficiently
The Array.BinarySearch method stops at the first element whose
IComparable.CompareTo results in a value of zero or higher.  If the compare
result is zero, BinarySearch returns the index.  If the compare is greater
than zero, BinarySearch returns the -1 * index.  (Strange, but hey, I didn't
write it.)

Therefore, when you call BinarySearch, you need to check the value returned
to see what the result is.  Note that in the example below, FindObj assumes
the array is sorted.  If you need to sort your array, there is a sort method
provided.

- - -

using System;
public class Demo
{
public static void FindObj( Array ary, Object obj )
{
int i = Array.BinarySearch( ary, obj );
if ( i < 0 )
{
i = ~i;
Console.WriteLine( "The object to search for ({0}) is not
found.", obj);
if (i < ary.GetUpperBound(0))
Console.WriteLine( "\tThe next larger object is at index
{0}.", i );
else
Console.WriteLine( "\tThere is no larger object");
if (i > ary.GetLowerBound(0))
Console.WriteLine( "\tThe next smaller object is at index
{0}.", --i );
else
Console.WriteLine( "\tThere is no smaller object");
}
else
Console.WriteLine( "The object to search for ({0}) is at index
{1}.", obj, i );
}

public static void Main()
{
Array myIntAry = Array.CreateInstance( typeof(Int32), 50 );
for ( int i = myIntAry.GetLowerBound(0); i <=
myIntAry.GetUpperBound(0); ++i )
myIntAry.SetValue( i*2, i ); // Fill with even numbers 0 through
100
myIntAry.Sort();

FindObj(myIntAry, 50); // Should find
FindObj(myIntAry, 51); // Not present, but there is one that is
larger and one that is smaller
FindObj(myIntAry, -3); // Not present, but there is one that is
larger
FindObj(myIntAry, 101); // Not present, but there is one that is
smaller
}

Quote:
}

- - -

Robert L. Ayers

"David Sworder (formerly known as "Rev. Dr. Hulio Manuel Sanchez-Cruz")"

Quote:

>     Actually, there is a method called Array.BinarySearch() which is
pretty
> close to what I'm looking for.

Wed, 30 Mar 2005 12:24:24 GMT
SortedList, searching for items efficiently

Quote:
> result is zero, BinarySearch returns the index.  If the compare is greater
> than zero, BinarySearch returns the -1 * index.  (Strange, but hey, I
didn't
> write it.)

Yeah, the whole "ones complement" thing struck me as kind of weird