BinarySearchとの相違点に最も近いインデックスを見つける

Question

私は約50万の並べ替えられた配列を持っています。現時点では、ターゲットのintとすべての要素の差をとり、LINQ（非常に非効率的）を使って最小の差でソートすることで、正しいインデックスを選択しています。

私はBinarySearchと非常によく似たことをしたいと思います。

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

私は値24のために最も近い値を検索する場合、私は、インデックスが指定された1

ように返さたい：

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

これは2を戻します

これは、最も近いものの代わりに、次の要素をラインに与えるからです。最も近いインデックスを返すIComparerを記述することは可能ですか？

与えられた値は：

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

は、私はできるだけ速くこれを行うにしようとしています。今まで私がLINQで行ってきたことはすべて、よく行われたバイナリ検索で達成できると思っていました。入力いただきありがとうございます。

Answer 1

ちょうどバイナリ検索を行い、その結果が負の場合、あなたはそれが挿入される場所を見つけて、次のと前回エントリを見て - つまり、あなたの現在のコードで、チェックindexとindex - 1（後indexが0でないことを確認してください:)。近くにあるものを見つけたら、あなたは完了です。

Answer 2

ここでは、John Skeetの説明に基づいた短いデモです。 このメソッドは、Timeと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; 

    }