BinarySearch ile fark en yakın endeksi bul

Question

Yaklaşık 500.000 ints dizilmiş bir dizi var. Şu anda, hedef int ve tüm elemanlar arasındaki farkları alarak ve sonra LINQ (çok verimsiz) kullanarak minimum farkla sıralama yaparak doğru indeksi seçiyorum.

BinarySearch ile çok benzer bir şey yapabilmek istiyorum.

Verilen:

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

Bu 2 döndürür:

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

ben endeksi isteyeyim değeri 24 için en yakın değeri bulmak istiyorsanız

1.

Verilen olmak döndü Bir sonraki elemanı en yakın yerine sırayla verdiğinden. En yakın dizini veren bir IComparer yazmak mümkün mü?

Verilen değerler:

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

ben mümkün olduğunca hızlı bu yapmaya çalışıyorum. LINQ'da şimdiye kadar yaptığım her şey, iyi yapılmış bir ikili arama ile elde edilebileceğine inanıyorum. Giriş için teşekkürler.

Answer 1

Sadece ikili arama yapmak ve sonuç negatif olup olmadığını o zaman ekleneceği nereye bulmak ve bir sonraki ve önceki girişi bakmak - diğer bir deyişle, mevcut kodu ile kontrol index ve index - 1 (sonra index'un 0 değil olduğunu kontrol etme. Daha yakın olanı bul ve bitirdin.

Answer 2

John Skeet'in açıklamasına dayanan kısa bir demo. Bu yöntem yalnızca Zaman ve Zaman arasında olan tarihleri ​​döndürür. Elbette, orijinal dizinin zamana göre sıralandığını varsayar.

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; 

    }