C# Algorithms – Find Index of Item Closest to Value but Less Than Value

algorithmsc

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.

Best 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.)

Related Topic