Ayúdame a escribir una búsqueda binaria de valores límite (extracción de sublistas)

Question

Digamos que tengo una gran variedad de valores (sintaxis C ++, lo siento):

vector<double> x(100000);

Esta matriz está ordenada de modo que x [n] > x [n-1] .

Me gustaría que una función recupere una matriz de todos los valores en el rango [a, b] (eso es inclusivo). Algunas interfaces como:

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

Cuando se completa esta función, sub contendrá los valores n que cayeron en el rango [a, b].

Por supuesto, una búsqueda lineal es fácil:

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]);
        }
    }
}

Sin embargo, debido a que data está ordenado, debería poder hacerlo mucho más rápido usando una búsqueda binaria. ¿Quién quiere apuñalarlo? ¡Se permite cualquier idioma!

Answer 1

Lo que estás preguntando es un poco confuso con respecto a las propiedades exactas del rango y los tipos. Sin embargo, puede ajustar el siguiente código C ++ para satisfacer sus necesidades. La intuición básica es usar lower_bound y upper_bound para encontrar las posiciones en la matriz que delinean el rango que está buscando.

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

Ya parece saber que una búsqueda binaria se puede utilizar para encontrar el rango, y las implementaciones de estos se encuentran fácilmente.

Todo lo demás es solo una manipulación trivial de la matriz.

Answer 3

La solución fácil:

• usa la búsqueda binaria para encontrar el valor más bajo ay el más alto b
• asignar una nueva matriz
• copia los valores

El código es trivial como se dijo anteriormente.