Finden Sie den nächsten Index durch den Unterschied mit BinarySearch

Question

Ich habe eine sortierte Array von etwa 500.000 Ints. Zur Zeit wähle ich den korrekten Index aus, indem ich die Unterschiede zwischen meinem Ziel int und allen Elementen nehme und dann mit LINQ (sehr ineffizient) nach der minimalen Differenz sortiere.

Ich möchte in der Lage sein, etwas sehr ähnliches mit BinarySearch zu tun.

Gegeben:

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

Wenn ich will, für Wert 24, um den nächsten Wert finden ich den Index möchte zurück 1.

gegeben werden:

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

Dieser Wert 2 da es das nächste Element in der Zeile statt dem nächsten gibt. Ist es möglich, einen IComparer zu schreiben, der den nächsten Index zurückgibt?

Gegebene Werte:

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

Ich versuche, diese so schnell wie möglich zu machen. Alles, was ich bisher in LINQ getan habe, war dem, was ich mit einer gut gemachten binären Suche erreichen kann, unterlegen. Danke für die Eingabe.

Answer 1

tun einfach die binäre Suche, und wenn das Ergebnis negativ ist, dass Sie dann finden, wo es eingeführt und an dem nächsten und vorherigen Eintrag aussehen würde - mit anderen Worten, mit dem aktuellen Code, überprüft index und index - 1 (nach Überprüfen, dass index nicht 0 ist :). Finde heraus, was näher ist, und du bist fertig.

Answer 2

Hier ist eine kurze Demo, basierend auf John Skeet Explantation. Diese Methode gibt nur Daten zwischen "Zeit" und "Uhrzeit" zurück. Es nimmt natürlich an, dass das ursprüngliche Array nach der Zeit sortiert ist.

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; 

    }