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.

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

1 Answer 1


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.
    – itsme86
    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.
    – OldFart
    Commented Aug 8, 2013 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.