459,914 Members | 1,718 Online
Need help? Post your question and get tips & solutions from a community of 459,914 IT Pros & Developers. It's quick & easy.

# find closest item in keyed collection

 P: n/a 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, Dec 17 '07 #1
22 Replies

 P: n/a Oops; "Single" should have been "First"... Marc Dec 17 '07 #2

 P: n/a Still dont understand why >=35 isnt 40... some new math I did miss? //CY Dec 17 '07 #3

 P: n/a If the poster is looking for the nearest property to a particular address, then his numbers may indeed be keys. Yes; I was thrown by the OP *only* mentioning a single series of numeric data, rather than two. I followed up with a post acknowledging this. Although lets be fair - a lot of things could have been a little clearer in the original question. Marc Dec 17 '07 #4

 P: n/a "Marc Gravell" wrote: If the poster is looking for the nearest property to a particular address, then his numbers may indeed be keys. Yes; I was thrown by the OP *only* mentioning a single series of numeric data, rather than two. I followed up with a post acknowledging this. Although lets be fair - a lot of things could have been a little clearer in the original question. Marc You are right on both counts. Sorry, I responded before seeing the other posts. You gave a slick solution. > Dec 17 '07 #5

 P: n/a "Steve Richter" = 35. would return the 30 key. Maintain a SortedList containing these keys, SortedList can find the closest (or following, or preceding) entry in O(log N) time. > thanks, Dec 17 '07 #6

 P: n/a "Ben Voigt [C++ MVP]" "Steve Richter" Does the .NET framework provide a class which will find the item inthe 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, 80find key which is >= 35.would return the 30 key. Maintain a SortedList containing these keys, SortedList can find the closest (or following, or preceding) entry in O(log N) time. with what method? do you mean by iterating the list ? I think the OP was looking for a function of the sort you used to see in xBASE dialects ... think it was called SOFTSEEK(), which would return either the key sought or the next highest-valued key, if any ... I'm not aware of such a function in the Framework Dec 17 '07 #7

 P: n/a On Dec 17, 5:46 pm, "Liz" = 35. would return the 30 key. Maintain a SortedList containing these keys, SortedList can find the closest (or following, or preceding) entry in O(log N) time. with what method? do you mean by iterating the list ? I think the OP was looking for a function of the sort you used to see in xBASE dialects ... think it was called SOFTSEEK(), which would return either the key sought or the next highest-valued key, if any ... I'm not aware of such a function in the Framework thanks for the responses ( and sorry for the confusion on what I intended as <= 35 ). what I have is a text file concatenated as a single string. As I scan and parse the string I want to be able to determine the line number and position in the line of any offset in the string. As I concat the text lines, the line number and start/end offset in the string of the line would be stored in a collection. When I find something at offset 2022 in the string, I want to find in the collection of "line numbers/ start offset in the string" the offset which is <= 2022. That would tell me the text file line number. -Steve Dec 18 '07 #8

 P: n/a 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...). 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

 P: n/a "Marc Gravell" 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

 P: n/a // Array.BinarySearch (find next closest match) Array i2 = Array.CreateInstance(typeof(string), 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); int j = Array.BinarySearch(i2, "DonnaB"); if (j<0) j = ~j; MessageBox.Show(i2.GetValue(j).ToString()); // ==Elizabeth "Ben Voigt [C++ MVP]" "Marc Gravell" One-way searches are fortunately easier than 2-way proximity... you getto stop sooner ;-pIf this is volume usage, then the LINQ approach I posted earlier would bea poor choice (it would sort each time); Ben mentioned a SortedList whichmay be helpful... I can't only see equality methods myself, but you couldperhaps simply walk the list until you find one that is 2022 and returnthe previous (if you see what I mean...). Ack! SortedList.IndexOfKey doesn't return the index for not found items, while List.BinarySearch 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.BinarySearch and keep the list sorted yourself. >>Of course, if you are adding to the list in sequence, you could just usea regular list, and do the same walk.If you are adding to the list while iterating, it is probably just thelast element.Just for completeness (to contrast to my prior post); in LINQ terms thisis: IDictionary

 P: n/a Ben, Tested that on the original q, as I understand it, the "close find" shuld give 40 if asked 39... Array i2 = Array.CreateInstance(typeof(short),7); // given 20, 30, 40, 50, 60, 70, 80 i2.SetValue((short)20, 0); i2.SetValue((short)30, 1); i2.SetValue((short)40, 2); i2.SetValue((short)50, 3); i2.SetValue((short)60, 4); i2.SetValue((short)70, 5); i2.SetValue((short)80, 6); // given 35 int j = Array.BinarySearch(i2, (short)35); if (j < -1) j = ~j-1; Console.WriteLine("35 -" + i2.GetValue(j).ToString()); // 30 // testing low 10 j = Array.BinarySearch(i2, (short)10); if (j < -1) j = ~j - 1; else // Oops j = 0; Console.WriteLine("10 -" + i2.GetValue(j).ToString()); // 20 // testing high 100 j = Array.BinarySearch(i2, (short)100); if (j < -1) j = ~j - 1; Console.WriteLine("100 -" + i2.GetValue(j).ToString()); // 80 // testing close 39 j = Array.BinarySearch(i2, (short)39); if (j < -1) j = ~j - 1; Console.WriteLine("39 -" + i2.GetValue(j).ToString()); // 30 = Fail, should return 40 or what? //CY Dec 19 '07 #12

 P: n/a Array i2 = Array.CreateInstance(typeof(short),7); // given 20, 30, 40, 50, 60, 70, 80 i2.SetValue((short)20, 0); i2.SetValue((short)30, 1); i2.SetValue((short)40, 2); i2.SetValue((short)50, 3); i2.SetValue((short)60, 4); i2.SetValue((short)70, 5); i2.SetValue((short)80, 6); // given 35 int j = Array.BinarySearch(i2, (short)35); if (j < -1) j = ~j-1; Console.WriteLine("35 -" + i2.GetValue(j).ToString()); // 30 // testing low 10 j = Array.BinarySearch(i2, (short)10); if (j < -1) j = ~j - 1; else // Oops j = 0; Console.WriteLine("10 -" + i2.GetValue(j).ToString()); // 20 // testing high 100 j = Array.BinarySearch(i2, (short)100); if (j < -1) j = ~j - 1; Console.WriteLine("100 -" + i2.GetValue(j).ToString()); // 80 // testing close 39 j = Array.BinarySearch(i2, (short)39); if (j < -1) j = ~j - 1; Console.WriteLine("39 -" + i2.GetValue(j).ToString()); // 30 = Fail, should return 40 or what? //CY Dec 19 '07 #13

 P: n/a "Liz" Ben, Tested that on the original q, as I understand it, the "closefind" 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.CreateInstance(typeof(short),7);// given 20, 30, 40, 50, 60, 70, 80 i2.SetValue((short)20, 0); i2.SetValue((short)30, 1); i2.SetValue((short)40, 2); i2.SetValue((short)50, 3); i2.SetValue((short)60, 4); i2.SetValue((short)70, 5); i2.SetValue((short)80, 6);// given 35 int j = Array.BinarySearch(i2, (short)35); if (j < -1) j = ~j-1; Console.WriteLine("35 -" +i2.GetValue(j).ToString()); // 30// testing low 10 j = Array.BinarySearch(i2, (short)10); if (j < -1) j = ~j - 1; else // Oops j = 0; Console.WriteLine("10 -" +i2.GetValue(j).ToString()); // 20// testing high 100 j = Array.BinarySearch(i2, (short)100); if (j < -1) j = ~j - 1; Console.WriteLine("100 -" +i2.GetValue(j).ToString()); // 80// testing close 39 j = Array.BinarySearch(i2, (short)39); if (j < -1) j = ~j - 1; Console.WriteLine("39 -" +i2.GetValue(j).ToString()); // 30 = Fail, should return 40 or what?//CY Dec 19 '07 #14

 P: n/a "Liz" // Array.BinarySearch (find next closest match) Array i2 = Array.CreateInstance(typeof(string), 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"}; Just curious Bill Dec 20 '07 #15

 P: n/a "Bill Butler" Array i2 = Array.CreateInstance(typeof(string), 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 (straightforward) 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 ... Dec 20 '07 #16

 P: n/a "Liz" "Bill Butler" >Array i2 = Array.CreateInstance(typeof(string), 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 aboutstring[] 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 (straightforward) 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.CreateInstance instead of the more common syntax for array creation? Is there some benefit that I am unaware of? As I said "Just Curious" Bill Dec 20 '07 #17

 P: n/a "Bill Butler" >How aboutstring[] X = new string[]{"Anne", "Bob", "Chris", "Donna", "Elizabeth","Glenn", "Franklin", "Helene"}; >The original question presented was how to get a "soft" match in an arrayusing BinarySearch, i.e.: if no match, return the next highest value inthe array; so far as I know, there's no (straightforward) way to getthere 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.CreateInstance 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.CreateInstance 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? Dec 20 '07 #18

 P: n/a "Liz" "Bill Butler" Bill, First of all, your comment was not off-topic .... >I simply wanted to know why you would Array.CreateInstance instead ofthe 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.BinarySearch(X,"DonnaZ"); Dec 20 '07 #19

 P: n/a On Wed, 19 Dec 2007 20:13:53 -0800, Liz I simply wanted to know why you would Array.CreateInstance instead ofthemore 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.BinarySearch() 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.BinarySearch. 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.BinarySearch(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 Dec 20 '07 #20

 P: n/a "Bill Butler" >I simply wanted to know why you would Array.CreateInstance instead ofthe 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 arrayinitialization syntax you propose here? Array.BinarySearch(X,"DonnaZ"); There ya go ... I learn something new every day :) I do think the string[] X = { ... } is more useful for relatively small lists like this example, though ... (where you really can just walk the array instead of using a BinarySearch) Dec 20 '07 #21

 P: n/a "Peter Duniho" > yeah, it's awkward but more because of the series of arr.SetValue(string, n); statements than anything else; I *don't* prefer it; my focus from the original question was the behavior of BinarySearch to fetch the next highest value on no-match ... not the mechanics of constructing the array to search << I'm at a loss to understand why you'd prefer that syntax to the normal array declaration syntax >> what do you consider "normal" ? string[] x = { a, b, c } is fine, but only for a smallish sample of known elements ... anyway, do you really think there's an incredible difference in readability or wieldiness in these two: string[] x = new string[4500]; for (int n = 0; n < 4500; n++) { x[n] = "Value" + n.ToString(); } Array x = Array.CreateInstance( typeof(string), 4500 ); for (int n = 0; n < 4500; n++) { x.SetValue( "Value" + n.ToString(), n ); } I think I'd give the first one a slight edge mainly because it has a more familiar feel to "C" family programmers .... but that's about it ... OTOH, it would be what I would normally use based on that familiarity factor ... Dec 20 '07 #22

 P: n/a On Wed, 19 Dec 2007 23:55:16 -0800, Liz > what do you consider "normal" ? string[] x = { a, b, c } is fine, but only for a smallish sample of known elements ... I don't know what that means. No matter how many elements you have, it's always easier to write a list of them, than to write a list of them contained in a long list of calls to Array.SetValue(). In the former case, you have each item, plus a comma and optionally a space. In the latter case, you have each item, plus a semi-colon, and optionally a space and/or newline, to which you also have to add the name of the array plusa period plus the method name "SetValue" plus a pair of parentheses. Can you describe a scenario in which the syntax you've offered is more compact or is in any describable way better than the normal syntax? And yes...the "string[] x = ..." syntax is definitely the normal syntax. You're the first person I've ever seen use the other syntax when the type of the array elements was known. anyway, do you really think there's an incredible difference in readability or wieldiness in these two: Yes, absolutely. I find the latter arbitrarily and significantly awkward. Besides, with the first example you get a variable that has the actual type of the array. With the latter, there's no compile-time protection against coding errors, nor do you get any help with Intellisense for that matter. I see literally no value at all in the second example, except of course when you don't know the array type in the first place (but then you couldn't write "typeof(string)"...you'd have to have an actual Type variable to pass in there). Pete Dec 20 '07 #23

### This discussion thread is closed

Replies have been disabled for this discussion.