境界値のバイナリ検索を作成するのに役立ちます（サブリストを抽出）

Question

多数の値の配列があるとしましょう（C ++構文、申し訳ありません）：

vector<double> x(100000);

この配列は、 x [n]＆gt;のようにソートされます。 x [n-1] 。

[a、b]の範囲内のすべての値の配列を取得する関数が必要です（これを含む）。次のようなインターフェース：

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

この関数が完了すると、 sub には、範囲[a、b]に含まれる 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 はソートされているため、バイナリ検索を使用してこれをはるかに高速に実行できるはずです。誰がそれを突き刺したいですか？すべての言語が許可されています！

Answer 1

あなたが尋ねているのは、正確な範囲のプロパティとタイプに関して少し混乱することです。ただし、ニーズに合わせて次の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);
}

Answer 2

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

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

Answer 3

簡単な解決策：

• バイナリ検索を使用して、最低のaと最高のbを見つけます
• 新しい配列を割り当てる
• 値をコピーする

前述のようにコードは簡単です。