Aidez-moi à écrire une recherche binaire pour les valeurs limites (extraction des listes de sous)

Question

Disons que j'ai un tableau de lots de valeurs (C++ de syntaxe, désolé):

vector<double> x(100000); 

Ce tableau est trié telle que x[n] > x[n-1].

Je voudrais qu'une fonction récupère un tableau de toutes les valeurs dans la plage [a, b] (c'est inclus). Certains comme l'interface:

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

Lorsque cette fonction est terminée, sub contiendra les n valeurs qui sont tombées dans l'intervalle [a, b].

Bien sûr une recherche linéaire est facile:

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

Cependant, parce que data est triée, je devrais être en mesure de le faire en utilisant beaucoup plus rapidement une recherche binaire. Qui veut prendre un coup de couteau? Toute langue est autorisée!

Answer 1

Ce que vous demandez est un peu déroutant en ce qui concerne les propriétés exactes de la gamme et les types. Cependant, vous pouvez modifier le code C++ suivant en fonction de vos besoins. L'intuition de base est d'utiliser lower_bound et upper_bound pour trouver les positions dans le tableau qui délimitent la plage que vous recherchez.

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

Vous semblez déjà savoir qu'une recherche binaire peut être utilisée pour trouver la plage, et les implémentations de ceux-ci sont faciles à trouver.

Tout le reste ne fait qu'obtenir une manipulation de matrice triviale.

Answer 3

La solution facile:

• utilisation recherche binaire pour trouver le plus bas a et le plus b
• allouent un nouveau tableau
• copier les valeurs

code

est trivial comme dit avant.