Find the closest index by difference with BinarySearch

Question

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

I would like to do something very similar to BinarySearch.

Given:

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

If I want to find the closest value to a value of 24, I would like the index to return equal to 1.

Given:

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

This returns 2 because it gives the next element in the string, not the closest. Is it possible to write IComparer that will return the closest index?

Indicated values:

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

I am trying to do this as quickly as possible. All that I have done so far in LINQ has been an approach to what, in my opinion, can be achieved with a well-done binary search. Thanks for the input.

Answer 1

Just do a binary search, and if the result is negative, you will find where it will be inserted and look at the next and previous record - in other words, with your current code check index and index - 1 (after checking that index not 0 :) . Find out what's closer and you're done.

Answer 2

Here is a short demo based on John Skeet's explanation. This method returns only dates that are between time and time. Of course, it is assumed 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; }