Inexact Binary Search: Given a Value, Find the Upper and Lower Index Of The Element Position
I have a List<KeyValuePair<double, double>>
, the list is sorted by KeyValuePair.Key
, so it's amendable to binary search. And I have a double
object. Now, my task is to find the index of the double
object. Here are the conditions that apply:
- If that
d开发者_开发百科ouble
object matches one of theKeyValuePair.Key
within a specified tolerance, then the correspondingKeyValuePair.Value
should be returned. - If the
double
object falls outside the max and min range ofKeyValuePair.Key
, then a 0 should be returned. - If the
double
object falls within the max min of theKeyValuePair.Key
, but not matched any of theKeyValuePair.Key
within a specified tolerance, then the get the average of the nearest upper and nearest lowerKeyValuePair.Value
( as measured byKeyValuePair.Key
).
I know that a binary search implementation is available in C#, but it is not exactly suited to my needs. I would like to ask is there any implementation out there that already meets my needs? I don't want to spend a few hours writing and debugging the code that other people has already written, debugged and perfected.
This can be done fairly easily with a comparer and a small wrapper around List<T>.BinarySearch
:
static double Search(List<KeyValuePair<double, double>> list, double key) {
int index = list.BinarySearch(
new KeyValuePair<double, double>(key, 0),
new Comparer());
// Case 1
if (index >= 0)
return list[index].Value;
// NOTE: if the search fails, List<T>.BinarySearch returns the
// bitwise complement of the insertion index that would be used
// to keep the list sorted.
index = ~index;
// Case 2
if (index == 0 || index == list.Count)
return 0;
// Case 3
return (list[index - 1].Value + list[index].Value) / 2;
}
class Comparer : IComparer<KeyValuePair<double, double>> {
public int Compare(
KeyValuePair<double, double> x,
KeyValuePair<double, double> y)
{
if (Math.abs(x.Key - y.Key) < TOLERANCE)
return 0;
return x.Key.CompareTo(y.Key);
}
}
精彩评论