Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
4  
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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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 Aug 7 '13 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 Aug 8 '13 at 15:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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