1

多くの値の配列があるとしましょう (C++ 構文、申し訳ありません)。

vector<double> x(100000);

この配列は次のようにソートされx[n] > x[n-1]ます。

[a, b] の範囲内のすべての値の配列を取得する関数が必要です (これは包括的です)。次のようないくつかのインターフェース：

void subarray(const double a, const double b, vector<double> &sub) {
    ...
}

この関数が完了すると、範囲 [a, b] に収まる値subが含まれます。n

もちろん、線形検索は簡単です。

void subarray(const double a, const double b, vector<double> &sub) {
    for (size_t i = 0; i < data.size(); i++) {
        if (a <= data[i] && data[i] <= b) {
            sub.push_back(data[i]);
        }
    }
}

ただし、dataソートされているため、バイナリ検索を使用してこれをはるかに高速に実行できるはずです。誰がそれを刺したいですか？どの言語も許可されています。

4

3 に答える 3

4

あなたが求めているのは、正確な範囲のプロパティと型に関して少し混乱しています。ただし、ニーズに合わせて次の C++ コードを微調整できます。基本的な直感は、lower_bound と upper_bound を使用して、探している範囲を表す配列内の位置を見つけることです。

void subarray(const double a, const double b, vector <double> &sub, vector <int> pn) {
    vector <int>::const_iterator begin, end;
    begin = lower_bound(pn.begin(), pn.end(), a);
    end = upper_bound(pn.begin(), pn.end(), b);
    sub.insert(sub.begin(), begin, end);
}
于 2008-11-04T08:30:59.613 に答える
0

バイナリ検索を使用して範囲を見つけることができることは既にご存じのようで、それらの実装は簡単に見つかります。

他のすべては、単純な配列操作を取得しているだけです。

于 2008-11-04T08:28:46.827 に答える
0

簡単な解決策：

  • 二分探索を使用して、最小の a と最大の b を見つけます
  • 新しい配列を割り当てる
  • 値をコピーします

前に述べたように、コードは簡単です。

于 2008-11-04T08:32:21.577 に答える