3

ソートされた配列doubleがあります。目標は、配列内のインデックスを見つけることです。<= search の値の値を含むもの。

たとえば、配列には{0, 5, 12, 34, 100}インデックス範囲 [0 .. 4] の数値が含まれます。

値 = 25 を検索します。そして、index=2 (12 から 34 の間の出現範囲) を取得したい

この場合、バイナリ検索を実行する方法がわかりません。

   public class MyComparer : IComparer<double>
    {
        public int Compare(double x, double y)
        {
            //<-------- ???
        }
    }

    public double[] spline_x;

    MyComparer cmpc = new MyComparer();
    int i=Array.BinarySearch(spline_x, x, cmpc);
4

2 に答える 2

12

二分検索で配列内の項目が見つからない場合、値よりも大きい最初の要素のインデックスのビットごとの補数である負の数が返されます。これを使用して範囲を見つける方法は次のとおりです。

double[] spline_x = { 0D, 5D, 12D, 34D, 100D };
int i = Array.BinarySearch(spline_x, 25);
if (i >= 0)
{
    // your number is in array
}
else
{
    int indexOfNearest = ~i;

    if (indexOfNearest == spline_x.Length)
    {
        // number is greater that last item
    }
    else if (indexOfNearest == 0)
    {
        // number is less than first item
    }
    else
    {
        // number is between (indexOfNearest - 1) and indexOfNearest
    }     
}
于 2013-02-18T06:58:35.317 に答える
0

C# には慣れていませんが、素朴な二分探索でうまくいき、最後の数値 <= N を見つけます。これは、問題で説明した境界です。

int find_last(int num, const vector<int>&v, size_t begin, size_t end) {
  if (begin >= end) {
    return -1;
  }
  size_t mid = (begin + end) / 2;
  if (v[mid] > num) {
    // [mid, end) is bigger than num, the boundary is in [begin, mid)
    return find_last(num, v, begin, mid);
  }
  // v[mid] is qualified as <= N, search [mid+1, end) for
  // approaching a better boundary if exists.
  size_t index = find_last(num, v, mid+1, end);
  return (index == -1 ? mid : index);
}
于 2013-02-26T03:25:06.920 に答える