Trouver l'index le plus proche par différence avec BinarySearch

Question

J'ai un tableau trié d'environ 500 000 ints. Actuellement, je sélectionne l'index correct en prenant les différences entre mon int cible, et tous les éléments, puis en triant par la différence minimale en utilisant LINQ (très inefficace). Je voudrais être en mesure de faire quelque chose de très similaire avec BinarySearch.

Vu:

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

Si je veux trouver la valeur la plus proche de la valeur 24 Je veux l'indice a été à 1.

Vu:

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

Cela renvoie 2 car il donne l'élément suivant en ligne, au lieu du plus proche. Est-il possible d'écrire un IComparer qui retournerait l'index le plus proche?

Valeurs données:

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

Je suis en train de faire ce aussi vite que possible. Tout ce que j'ai fait jusqu'ici dans LINQ a été inférieur à ce que je pense que l'on peut réaliser avec une recherche binaire bien faite. Merci de votre contribution.

Answer 1

Il suffit de faire la recherche binaire, et si le résultat est vous alors trouver négatif où il serait inséré et regarder la prochaine entrée et précédent - en d'autres termes, avec votre code actuel, vérifiez index et index - 1 (après vérifier que index n'est pas 0 :). Découvrez ce qui est le plus proche, et vous avez terminé.

Answer 2

Voici une courte démonstration, basée sur l'explantation de John Skeet. Cette méthode renvoie uniquement les dates comprises entre Heure et Heure. Il suppose bien sûr que le tableau original est trié par heure.

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; 

    }