int value = 35;
int[] list = new[] { 1, 8, 13, 20, 25, 32, 50, 55, 64, 70 };
int? floor = null;
int? ceil = null;
int index = Array.BinarySearch(list, value);
if (index >= 0) // element is found
{
if (index > 0)
floor = list[index - 1];
if (index < list.Length - 1)
ceil = list[index + 1];
}
else
{
index = ~index;
if (index < list.Length)
ceil = list[index];
if (index > 0)
floor = list[index - 1];
}
Console.WriteLine("floor = {0}", floor);
Console.WriteLine("ceil = {0}", ceil);
What is the best way to find the nearest lesser and greater values in a list to a given number
문제
I have a random list of numbers say 1,8,13,20,25,32,50,55,64,70 now given a number say 35 the lesser value required will be 32 and greater value will be 50.
the way I tried to do this is by iterating all the values
var value = 35;
var list = new List<int> { 1, 8, 13, 20, 25, 32, 50, 55, 64, 70 };
var lesser = list.First();
var greater = list.Last();
foreach (var curr in list)
{
if (curr >= value)
{
greater = curr;
break;
}
lesser = curr;
}
Console.WriteLine("Lesser Value :{0}\tGreater Value:{1}", lesser, greater);
Now the reason why I am asking this is I need to optimize for a situation where the list is generated once and then values are requested multiple times. Iterating the list for each request seems like a bad idea.
Update
The question did not specify what is required if we get an exact match, I needed the upper and lower bounds to be the matched element in that case ie, 32 should return 32 as the lesser value and 32 as the greater value in the above list.
The modified answer to reflect the same is :
int value = 32;
int[] list = new[] { 1, 8, 13, 20, 25, 32, 50, 55, 64, 70 };
int? floor = null;
int? ceil = null;
int index = Array.BinarySearch(list, value);
if (index >= 0) // element is found
{
floor = ceil =list[index] ;
}
else
{
index = ~index;
if (index == list.Length)
{
ceil = floor = list[index-1];
}
else
{
ceil = list[index];
floor = list[((index==0)?index: index-1)];
}
}
Console.WriteLine("floor = {0}", floor);
Console.WriteLine("ceil = {0}", ceil);
해결책
다른 팁
If list is sorted, you can do like this:
int value = 35;
var lessThan = list.TakeWhile(p => p < value).LastOrDefault();
var greaterThan = list.SkipWhile(p => p <= value).FirstOrDefault();