find closest item in keyed collection

[Steve Richter]

Does the .NET framework provide a class which will find the item in
the collection with a key which is closest ( greater than or equal,
less than or equal ) to the keys of the collection?

ex: collection keys are 20, 30, 40, 50, 60, 70, 80

find key which is >= 35.

would return the 30 key.

thanks,

[Liz]

// Array.BinarySea rch (find next closest match)

Array i2 = Array.CreateIns tance(typeof(st ring), 8);

i2.SetValue("An ne", 0);
i2.SetValue("Bo b", 1);
i2.SetValue("Ch ris", 2);
i2.SetValue("Do nna", 3);
i2.SetValue("El izabeth", 4);
i2.SetValue("Gl enn", 5);
i2.SetValue("Fr anklin", 6);
i2.SetValue("He lene", 7);

int j = Array.BinarySea rch(i2, "DonnaB");
if (j<0)
j = ~j;

MessageBox.Show (i2.GetValue(j) .ToString()); // ==Elizabeth


"Ben Voigt [C++ MVP]" <rb*@nospam.nos pamwrote in message
news:O6******** ******@TK2MSFTN GP05.phx.gbl...

>
"Marc Gravell" <ma**********@g mail.comwrote in message
news:%2******** ********@TK2MSF TNGP03.phx.gbl. ..

>One-way searches are fortunately easier than 2-way proximity... you get
to stop sooner ;-p
If this is volume usage, then the LINQ approach I posted earlier would be
a poor choice (it would sort each time); Ben mentioned a SortedList which
may be helpful... I can't only see equality methods myself, but you could
perhaps simply walk the list until you find one that is 2022 and return
the previous (if you see what I mean...).

Ack! SortedList.Inde xOfKey doesn't return the index for not found items,
while List.BinarySear ch does. But you can't run BinarySearch on a sorted
list! An extension method would be good...

So either reimplement BinarySearch to work on a SortedList or use List and
List.BinarySear ch and keep the list sorted yourself.

>>
Of course, if you are adding to the list in sequence, you could just use
a regular list, and do the same walk.
If you are adding to the list while iterating, it is probably just the
last element.

Just for completeness (to contrast to my prior post); in LINQ terms this
is:

IDictionary<int , stringdata = new SortedList<int, string{
{20, "a"}, {30, "b"}, {40, "c"}, {50, "d"},
{60, "e"}, {70, "f"}, {80, "g"}
};
KeyValuePair<in t, stringresult =
data.TakeWhile( x =x.Key <= 35).Last();

(I'm using TakeWhile here since we know the data is sorted; hence it will
stop reading when it finds something that doesn't meet the <= 35
condition).

Of course, if you are generally accessing recent data you may be better
keeping the list inverted (perhaps even just a List<Tand Insert at 0;
or use a custom comparer to automatically invert the list in-place [very
easy]) and check for the first match:

KeyValuePair<in t, stringresult =
data.SkipWhile( x =x.Key 35).First();

Marc

[christery]

Ben, Tested that on the original q, as I understand it, the "close
find" shuld give 40 if asked 39...

Array i2 = Array.CreateIns tance(typeof(sh ort),7);

// given 20, 30, 40, 50, 60, 70, 80

i2.SetValue((sh ort)20, 0);
i2.SetValue((sh ort)30, 1);
i2.SetValue((sh ort)40, 2);
i2.SetValue((sh ort)50, 3);
i2.SetValue((sh ort)60, 4);
i2.SetValue((sh ort)70, 5);
i2.SetValue((sh ort)80, 6);

// given 35
int j = Array.BinarySea rch(i2, (short)35);
if (j < -1)
j = ~j-1;

Console.WriteLi ne("35 -" +
i2.GetValue(j). ToString()); // 30

// testing low 10
j = Array.BinarySea rch(i2, (short)10);
if (j < -1)
j = ~j - 1;
else // Oops
j = 0;
Console.WriteLi ne("10 -" +
i2.GetValue(j). ToString()); // 20

// testing high 100
j = Array.BinarySea rch(i2, (short)100);
if (j < -1)
j = ~j - 1;

Console.WriteLi ne("100 -" +
i2.GetValue(j). ToString()); // 80

// testing close 39
j = Array.BinarySea rch(i2, (short)39);
if (j < -1)
j = ~j - 1;

Console.WriteLi ne("39 -" +
i2.GetValue(j). ToString()); // 30 = Fail, should return 40 or what?

//CY

[Liz]

<ch*******@gmai l.comwrote in message
news:1d******** *************** ***********@1g2 000hsl.googlegr oups.com...

Ben, Tested that on the original q, as I understand it, the "close
find" shuld give 40 if asked 39...

that was my doing, not Ben's; yes, you should get 40 if the predicate is
39, and you do; what I'm not clear on is why you're subtracting 1 from the
bitwise complement of the result ... and why you're testing for "j < -1"

if (j < -1)
j = ~j-1;

should be:

if (j < 0)
j = ~j;

BUT, I should have done some bounds checking where the predicate is greater
than the highest valued item in the array:

if (j < i2.Length)
MessageBox.Show (i2.GetValue(j) .ToString());
else
MessageBox.Show ("Cannot return a value");

>
Array i2 = Array.CreateIns tance(typeof(sh ort),7);

// given 20, 30, 40, 50, 60, 70, 80

i2.SetValue((sh ort)20, 0);
i2.SetValue((sh ort)30, 1);
i2.SetValue((sh ort)40, 2);
i2.SetValue((sh ort)50, 3);
i2.SetValue((sh ort)60, 4);
i2.SetValue((sh ort)70, 5);
i2.SetValue((sh ort)80, 6);

// given 35
int j = Array.BinarySea rch(i2, (short)35);
if (j < -1)
j = ~j-1;

Console.WriteLi ne("35 -" +
i2.GetValue(j). ToString()); // 30

// testing low 10
j = Array.BinarySea rch(i2, (short)10);
if (j < -1)
j = ~j - 1;
else // Oops
j = 0;
Console.WriteLi ne("10 -" +
i2.GetValue(j). ToString()); // 20

// testing high 100
j = Array.BinarySea rch(i2, (short)100);
if (j < -1)
j = ~j - 1;

Console.WriteLi ne("100 -" +
i2.GetValue(j). ToString()); // 80

// testing close 39
j = Array.BinarySea rch(i2, (short)39);
if (j < -1)
j = ~j - 1;

Console.WriteLi ne("39 -" +
i2.GetValue(j). ToString()); // 30 = Fail, should return 40 or what?

//CY

[Ben Voigt [C++ MVP]]

"Liz" <li*@tiredofspa m.comwrote in message
news:%2******** ********@TK2MSF TNGP03.phx.gbl. ..

>
<ch*******@gmai l.comwrote in message
news:1d******** *************** ***********@1g2 000hsl.googlegr oups.com...

>Ben, Tested that on the original q, as I understand it, the "close
find" shuld give 40 if asked 39...

BinarySearch doesn't give you the closest element by default, it gives you
the address of the closest greater element. The element right before is
(due to sorting) the closest smaller element, and you may therefore use
whichever of the two you prefer. This is still O(log N), because there is
no extra expense as the length of the list increases.

If your list is less than about 64 elements you are better off with a single
pass linear search.

If your elements are fairly evenly distributed (or according to a known
distribution) then you can do much better than a binary search by estimating
the location of the element sought.

>
that was my doing, not Ben's; yes, you should get 40 if the predicate is
39, and you do; what I'm not clear on is why you're subtracting 1 from
the bitwise complement of the result ... and why you're testing for "j
< -1"

>if (j < -1)
j = ~j-1;

should be:

if (j < 0)
j = ~j;

BUT, I should have done some bounds checking where the predicate is
greater than the highest valued item in the array:

if (j < i2.Length)
MessageBox.Show (i2.GetValue(j) .ToString());
else
MessageBox.Show ("Cannot return a value");

>>
Array i2 = Array.CreateIns tance(typeof(sh ort),7);

// given 20, 30, 40, 50, 60, 70, 80

i2.SetValue((sh ort)20, 0);
i2.SetValue((sh ort)30, 1);
i2.SetValue((sh ort)40, 2);
i2.SetValue((sh ort)50, 3);
i2.SetValue((sh ort)60, 4);
i2.SetValue((sh ort)70, 5);
i2.SetValue((sh ort)80, 6);

// given 35
int j = Array.BinarySea rch(i2, (short)35);
if (j < -1)
j = ~j-1;

Console.WriteLi ne("35 -" +
i2.GetValue(j) .ToString()); // 30

// testing low 10
j = Array.BinarySea rch(i2, (short)10);
if (j < -1)
j = ~j - 1;
else // Oops
j = 0;
Console.WriteLi ne("10 -" +
i2.GetValue(j) .ToString()); // 20

// testing high 100
j = Array.BinarySea rch(i2, (short)100);
if (j < -1)
j = ~j - 1;

Console.WriteLi ne("100 -" +
i2.GetValue(j) .ToString()); // 80

// testing close 39
j = Array.BinarySea rch(i2, (short)39);
if (j < -1)
j = ~j - 1;

Console.WriteLi ne("39 -" +
i2.GetValue(j) .ToString()); // 30 = Fail, should return 40 or what?

//CY

[Bill Butler]

"Liz" <li*@tiredofspa m.comwrote in message
news:uC******** ******@TK2MSFTN GP03.phx.gbl...

>
// Array.BinarySea rch (find next closest match)

Array i2 = Array.CreateIns tance(typeof(st ring), 8);

i2.SetValue("An ne", 0);
i2.SetValue("Bo b", 1);
i2.SetValue("Ch ris", 2);
i2.SetValue("Do nna", 3);
i2.SetValue("El izabeth", 4);
i2.SetValue("Gl enn", 5);
i2.SetValue("Fr anklin", 6);
i2.SetValue("He lene", 7);

<snip>
<off topic>
Why would you declare an array of strings with that syntax?
I mean, it works, but why subject yourself to that icky looking code.
How about
string[] X = new string[]{"Anne", "Bob", "Chris", "Donna", "Elizabeth" ,
"Glenn", "Franklin", "Helene"};

Just curious
Bill

[Liz]

"Bill Butler" <qw****@asdf.co mwrote in message
news:Dikaj.8038 $8y4.8009@trndd c07...

>Array i2 = Array.CreateIns tance(typeof(st ring), 8);

i2.SetValue("A nne", 0);
i2.SetValue("B ob", 1);
i2.SetValue("C hris", 2);
i2.SetValue("D onna", 3);
i2.SetValue("E lizabeth", 4);
i2.SetValue("G lenn", 5);
i2.SetValue("F ranklin", 6);
i2.SetValue("H elene", 7);

Why would you declare an array of strings with that syntax?
I mean, it works, but why subject yourself to that icky looking code.

How about
string[] X = new string[]{"Anne", "Bob", "Chris", "Donna", "Elizabeth" ,
"Glenn", "Franklin", "Helene"};

The original question presented was how to get a "soft" match in an array
using BinarySearch, i.e.: if no match, return the next highest value in the
array; so far as I know, there's no (straightforwar d) way to get there from
string[] x = {..,..,.. } syntax ...

who cares about the "ickiness" of syntax? it's all machine code out the
door; in a real-world example, you'd iterate it up with no muss, no fuss in
5-10 lines of code wrapping array.SetValue( a,n) in a loop ... but if you
have a better solution to do the soft match, I'm all ears ... assume the
array would be of significant size, not length = 8 ...

[Bill Butler]

"Liz" <li*@tiredofspa m.comwrote in message
news:Oe******** ******@TK2MSFTN GP04.phx.gbl...

>
"Bill Butler" <qw****@asdf.co mwrote in message
news:Dikaj.8038 $8y4.8009@trndd c07...

>>Array i2 = Array.CreateIns tance(typeof(st ring), 8);

i2.SetValue(" Anne", 0);
i2.SetValue(" Bob", 1);
i2.SetValue(" Chris", 2);
i2.SetValue(" Donna", 3);
i2.SetValue(" Elizabeth", 4);
i2.SetValue(" Glenn", 5);
i2.SetValue(" Franklin", 6);
i2.SetValue(" Helene", 7);

>Why would you declare an array of strings with that syntax?
I mean, it works, but why subject yourself to that icky looking code.

>How about
string[] X = new string[]{"Anne", "Bob", "Chris", "Donna",
"Elizabeth" , "Glenn", "Franklin", "Helene"};

The original question presented was how to get a "soft" match in an
array using BinarySearch, i.e.: if no match, return the next highest
value in the array; so far as I know, there's no (straightforwar d)
way to get there from string[] x = {..,..,.. } syntax ...

I did Add "off topic" right before I asked (which you edited out).
I have no quibble over the Binary search suggestion, It is what I would
have suggested.
My question has nothing to do with that.
I simply wanted to know why you would Array.CreateIns tance instead of
the more common syntax for array creation?
Is there some benefit that I am unaware of?

As I said "Just Curious"

Bill

[Liz]

"Bill Butler" <qw****@asdf.co mwrote in message
news:jQlaj.2881 4$JW4.27575@trn ddc05...

>>How about
string[] X = new string[]{"Anne", "Bob", "Chris", "Donna", "Elizabeth" ,
"Glenn", "Franklin", "Helene"};

>The original question presented was how to get a "soft" match in an array
using BinarySearch, i.e.: if no match, return the next highest value in
the array; so far as I know, there's no (straightforwar d) way to get
there from string[] x = {..,..,.. } syntax ...

I did Add "off topic" right before I asked (which you edited out).
I have no quibble over the Binary search suggestion, It is what I would
have suggested.
My question has nothing to do with that.
I simply wanted to know why you would Array.CreateIns tance instead of the
more common syntax for array creation?
Is there some benefit that I am unaware of?

Bill,

First of all, your comment was not off-topic ....

I simply wanted to know why you would Array.CreateIns tance instead of the
more common syntax for array creation?

that's what I responded to .... you can't do this:

string[] X = new string[]{"Anne", "Bob", "Chris", "Donna",
"Elizabeth" , "Glenn", "Franklin", "Helene"};

X.BinarySearch( "DonnaZ");

Do you know a way to initiate a BinarySearch using the array initialization
syntax you propose here?

[Bill Butler]

"Liz" <li*@tiredofspa m.comwrote in message
news:%2******** *******@TK2MSFT NGP03.phx.gbl.. .

>
"Bill Butler" <qw****@asdf.co mwrote in message
news:jQlaj.2881 4$JW4.27575@trn ddc05...

<snip>

Bill,

First of all, your comment was not off-topic ....

>I simply wanted to know why you would Array.CreateIns tance instead of
the more common syntax for array creation?

that's what I responded to .... you can't do this:

string[] X = new string[]{"Anne", "Bob", "Chris", "Donna",
"Elizabeth" , "Glenn", "Franklin", "Helene"};

X.BinarySearch( "DonnaZ");

Do you know a way to initiate a BinarySearch using the array
initialization syntax you propose here?

Array.BinarySea rch(X,"DonnaZ") ;

[Peter Duniho]

On Wed, 19 Dec 2007 20:13:53 -0800, Liz <li*@tiredofspa m.comwrote:

[...]

>I simply wanted to know why you would Array.CreateIns tance instead of
the
more common syntax for array creation?

that's what I responded to .... you can't do this:

string[] X = new string[]{"Anne", "Bob", "Chris", "Donna",
"Elizabeth" , "Glenn", "Franklin", "Helene"};

X.BinarySearch( "DonnaZ");

You can't do that even initializing the array as you did. There's no
Array.BinarySea rch() overload that takes a single parameter. There's not
even an instance method version of BinarySearch.

Do you know a way to initiate a BinarySearch using the array
initialization
syntax you propose here?

There are a number of overloads for Array.BinarySea rch. Any of them would
work equally well, whether you initialize the array using the syntax you
posted or the syntax Bill posted. For example:

Array.BinarySea rch(X, "DonnaZ");

I'm with Bill. I don't see any advantage at all to using the syntax you
posted. It's incredibly unwieldy, difficult to read, and doesn't even
provide a typed array. I'm at a loss to understand why you'd prefer that
syntax to the normal array declaration syntax.

Pete