# 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)
{
if (address < area.Size)
return area;
address -= area.Size;
}

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
Commented Aug 7, 2013 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. Commented Aug 7, 2013 at 21:01

## 1 Answer

This calls for a straightforward binary search - only instead of returning failure when the bounds converge without a hit, you return the next lowest index. (Unless the total number of values is so small that it easily fits into memory - then a complete cache is the way to go.)

• Thanks, I'll give the binary search a shot. I'm using a 16-bit address space so a full cache might be a bit much. Commented Aug 7, 2013 at 21:08
• Array.BinarySearch already does what you want. If there is a hit, it returns the index of the hit. If there is a miss it returns the one's complement of the insertion index. Commented Aug 8, 2013 at 15:25