Помогите мне написать бинарный поиск для граничных значений (извлечение подсписков)

Question

Допустим, у меня есть массив с множеством значений (синтаксис C ++, извините):

vector<double> x(100000);

Этот массив отсортирован так, что x[n] > x[n-1].

Я бы хотел, чтобы функция извлекала массив всех значений в диапазоне [a, b] (это включительно). Какой-то интерфейс, например:

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

Когда эта функция завершится, sub будет содержать значения n, попавшие в диапазон [a, b].

Конечно, линейный поиск прост:

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

Простое решение:

• используйте бинарный поиск, чтобы найти самые низкие a и самые высокие b * 1004
• выделить новый массив
• скопировать значения

Код, как уже было сказано, тривиален.

Answer 3

Похоже, вы уже знаете, что для поиска диапазона можно использовать двоичный поиск, и его реализации легко найти.

Все остальное - просто тривиальные манипуляции с массивами.