Find closest index by difference with BinarySearch

Question

I have a sorted array of about 500,000 ints. Currently I am selecting the correct index by taking the differences between my target int, and all of the elements, and then sorting by the minimum difference using LINQ (very inefficient).

I'd like to be able to do something very similar with BinarySearch.

Given:

Pos Value
0   10
1   20
2   30
4   50
5   60

If I want to find the closest value for value 24 I would want the index returned to be 1.

Given:

int index = myArray.BinarySearch(values, 24);
if (index < 0)
    index = ~index;

This returns 2 since it gives the next element in line, instead of the closest. Is it possible to write an IComparer that would return the closest index?

Given values:

Value ExpectedReturn
20    1
24    1
25    2
26    2
30    2

I am trying to make this as fast as possible. Everything I have done so far in LINQ has been sub par to what I think can be achieved with a well done binary search. Thank you for the input.

Answer 1

Just do the binary search, and if the result is negative you then find where it would be inserted and look at the next and previous entry - in other words, with your current code, check index and index - 1 (after checking that index isn't 0 :). Find out which is closer, and you're done.

Answer 2

Here is a short demo , based on John Skeet's explantation. This method returns only dates that are between from Time and to Time. It assumes of course that the original array is sorted by time.

private DateTime[] GetDataForEntityInInterval(DateTime fromTime, DateTime toTime)
        {

        DateTime[] allValues = GetAllValuesFromDB();
        int indexFrom = Array.BinarySearch(allValues, fromTime);

         if(indexFrom < 0)
         {
             int indexOfNearest = ~indexFrom;

             if (indexOfNearest == allValues.Length)
             {
                 //from time is larger than all elements
                 return null;
             }
             else if (indexOfNearest == 0)
             {
                 // from time is less than first item
                 indexFrom = 0;
             }
             else
             {
                 // from time is between (indexOfNearest - 1) and indexOfNearest
                 indexFrom = indexOfNearest;
             }
         }

         int indexTo = Array.BinarySearch(allValues, toTime);
         if (indexTo < 0)
         {
             int indexOfNearest = ~indexTo;

             if (indexOfNearest == allValues.Length)
             {
                 //to time is larger than all elements
                 indexTo = allValues.Length - 1;
             }
             else if (indexOfNearest == 0)
             {
                 // to time is less than first item
                 return null;
             }
             else
             {
                 // to time is between (indexOfNearest - 1) and indexOfNearest
                 indexTo = Math.Max(0, indexOfNearest - 1);
             }
         }

        int length = indexTo - indexFrom + 1;
        DateTime[] result = new DateTime[length];
        if (length > 0)
        {
            Array.Copy(allValues, indexFrom, result, 0, length);
        }
        return result;

    }