C# と VB.NET の質問掲示板

お世話になります。

昇順ソート済みの配列で指定値を越える最初の要素のインデックスを高速に取得したいと思っています。
C#のバージョンは2010、.NET Framework は4 Client Profileです。

具体的には下記のような動作をさせたいです。

    double[] ar1 = { 0.0, 0.0, 1.0, 2.0, 2.0, 2.0, 4.0, 4.0, 4.0, 4.0 };
    double[] ar2 = { 0.0, 0.0, 1.0, 2.0, 3.0, 3.0, 4.0, 4.0, 4.0, 4.0 };
    double[] ar3 = { 0.0, 0.0, 1.0, 2.0, 3.0, 3.0,  };

    int index1 = Array.FindIndex(ar1, x => x > 3);  // 6が返る
    int index2 = Array.FindIndex(ar2, x => x > 3);  // 6が返る
    int index3 = Array.FindIndex(ar3, x => x > 3);  // -1が返る(見つからなかった)

御覧のようにArray.FindIndexで実現できることですが、計算量がO(n)になってしまいます。
与えられる配列の要素数は最大で3000ほどあります。
そこで、少しでも高速化するためにバイナリサーチを行いたいと考えています。

Array.BinarySearchで一致する要素が見つからなかった場合の仕様は下記の通りです。
・value より大きい値がある場合は、最初の大きい要素のインデックスのビットごとの補数
・value より大きい値が無い場合は、配列の要素数のビットごとの補数

このことを利用して、下記の実装を行いました。

まず、値が等しい場合に小さいと偽るIComparer<T>を実装しました。

    // 値が等しい場合に小さいと偽るIComparer実装
    public class GreaterCompare : IComparer<double>
    {
        public int Compare(double x, double y)
        {
            return (x <= y) ? -1 : 1;
        }
    }

そして、それを使って検索するメソッドを実装しました。

    // 指定値より大きい最初の要素のインデックスを返す(バイナリサーチ版)
    int FindGreater(double[] array, double value)
    {
        int index = ~Array.BinarySearch(array, value, new GreaterCompare());
        return (index < array.Length) ? index : -1; 
    }

GreaterCompareが値が等しい場合に小さいと偽るので、一致する値は絶対に見つかりません。
その結果、最初の大きい要素のインデックス(大きい値がない場合は要素数)のビットごとの補数が返ってきます。

これを加工して戻り値としています。

一通り試しましたが正常に動作しているようです。
が、もっと良い方法があるような気がしています。

これよりスマートで速い方法はありますでしょうか?
少しでも速くしたいのです。
#性能評価はまだ先ですが、クライアントからこの部分は出来るだけ速くという注文があるのです。

ヒントだけでもご教示いただけたら嬉しいです。
よろしくお願い致します。