Encuentra el índice más cercano por diferencia con BinarySearch

Question

Tengo una matriz ordenada de aproximadamente 500,000 ints. Actualmente selecciono el índice correcto tomando las diferencias entre mi int objetivo y todos los elementos, y luego ordenando por la diferencia mínima usando LINQ (muy ineficiente).

Me gustaría poder hacer algo muy similar con BinarySearch.

Dado:

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

Si quiero encontrar el valor más cercano para el valor 24 Me gustaría que el índice volvió a ser 1.

Dado:

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

Esto devuelve 2 ya que le da al siguiente elemento en línea, en lugar de al más cercano. ¿Es posible escribir un IComparer que devuelva el índice más cercano?

Dados los valores:

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

estoy tratando de hacer esto lo más rápido posible. Todo lo que he hecho hasta ahora en LINQ ha sido inferior a lo que creo que se puede lograr con una búsqueda binaria bien hecha. Gracias por la aportación.

Answer 1

Eso sí, la búsqueda binaria, y si el resultado es negativo, a continuación, encontrar donde se inserta y un vistazo a la siguiente entrada y anterior - en otras palabras, con su código actual, comprobar index y index - 1 (después de comprobando que index no es 0 :). Averigua cuál está más cerca y listo.

Answer 2

Aquí hay una breve demostración, basada en la explantación de John Skeet. Este método devuelve solo las fechas que están entre Hora y Tiempo. Supone por supuesto que la matriz original está ordenada por tiempo.

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; 

    }