# Find index of item closest to value, but is also less than value

Let's say I have a sorted array of ints like so:

``````int[] numbers = new[] { 10, 20, 27, 30, 55, 70 };
``````

What is the most efficient way, given a value, to find the value in that array (or the index of it) that is closest to the value but is not greater than the value?

For instance, given the value 26, it would return the 20.

Please note that the values in the array are dynamically assigned once when the program starts, but will not change for the duration of the program.

The simple solution that I'm using now is this:

``````int GetNumber(int value)
{
foreach (int number in numbers)
{
if ((value -= number) <= 0)
return number;
}

return -1;
}
``````

It works, but it's not extremely fast. I'm hoping there's some kind of algorithm that allows me to "map" values to ranges or something that will make lookups faster.

If it helps to know, I've used simple ints in my example, but the actual project I'm working on is a kind of segmented memory space where each of the segments are adjoined, but are of various sizes. This algorithm would allow me to pass in a memory address and get back the corresponding memory segment.

This is the actual method that is currently in use:

``````public MappedMemoryArea GetArea(int address)
{
foreach (MappedMemoryArea area in _areas)
{
return area;
}

return null;
}
``````

I have full control over the MappedMemoryArea type, so if adding a property to it would be beneficial for this purpose, it's totally doable.

-
Maybe a binary search? – Mike Aug 7 '13 at 20:36
Your both code examples do the different things than you are asking - they both find the first occurrence before which the sum of numbers is less than the given number. If this is your goal, both code are already the fastest way of doing it. – Codism Aug 7 '13 at 21:01