Fondements et Architecture des Boucles
La recherche dichotomique exploite la propriété de monotonie d'une séquence ou d'une fonction objectif pour diviser l'espace de recherche par deux à chaque itération. Cette approche garantit une complexité temporelle logarithmique O(log N), la rendant indispensable pour les contraintes de temps strictes typiques des environnements compétitifs.
Distinction entre Types Numériques
Le traitement des nombres flottants diffère fondamentalement des entiers. Là où la comparaison exacte est impossible sur les réels, on impose une tolérance d'erreur (epsilon) pour déterminer la convergence. L'intervalle se referme tant que l'écart entre les bornes dépasse cette marge critique.
#include <iostream>
#include <cmath>
constexpr double EPSILON = 1e-8;
double rechercher_réel(double borne_inf, double borne_sup) {
while (borne_inf < borne_sup - EPSILON) {
double milieu = (borne_inf + borne_sup) / 2.0;
if (propriété_validée(milieu)) {
borne_sup = milieu;
} else {
borne_inf = milieu;
}
}
return borne_sup;
}
Gestion Discrète et Choix de l'Arrondi
Pour les valeurs entières, la précision doit être absolue. La direction de convergence dépend de la manière dont la fonction de validation partitionne l'intervalle actuel. Deux schémas complémentaires couvrent l'ensemble des cas d'usage.
// Convergence vers la borne gauche première valide
int trouver_borne_gauche(int idx_min, int idx_max) {
while (idx_min < idx_max) {
int milieu = idx_min + (idx_max - idx_min) / 2;
if (est_faisable(milieu)) {
idx_max = milieu;
} else {
idx_min = milieu + 1;
}
}
return idx_min;
}
// Convergence vers la borne droite dernière valide
int trouver_borne_droite(int idx_min, int idx_max) {
while (idx_min < idx_max) {
int milieu = idx_min + (idx_max - idx_min + 1) / 2;
if (est_faisable(milieu)) {
idx_min = milieu;
} else {
idx_max = milieu - 1;
}
}
return idx_min;
}
Intégration avec les Conteneurs Standard
Plutôt que de maintenir des boucles personnalisées sur des tableaux triés, la bibliothèque standard offre des primitives hautement optimisées dans <algorithm>. Ces méthodes retournent des itérateurs pointant vers la première occurrence respectant un critère précis, éliminant ainsi les risques d'erreurs off-by-one.
std::lower_bound(vecteur.begin(), vecteur.end(), cible): adresse du premier élément ≥ cible.std::upper_bound(vecteur.begin(), vecteur.end(), cible): adresse du premier élément strictement > cible.
La soustraction de l'itérateur de début fournit directement l'indice discret correspondant. Ces outils restent neutres quant au type de propriété testée, mais exigent impérativement un jeu de données préalablement ordonné.
Modélisations Algoirthmiques Typiques
1. Maximisation sous Contrainte Globale
Ce pattern vise à trouver la dimension maximale permettant de découper au moins K pièces issues de rectangles de tailles variées. La fonction de validation agrège les quotas potentiellement extraits et compare la somme totale à l'objectif requis.
#include <iostream>
#include <vector>
#include <algorithm>
using Int64 = long long;
struct Dimension {
int largeur, hauteur;
};
bool vérifier_quota(const std::vector<Dimension>& sources, const Int64 nb_pieux_requis, int côté_minimal) {
Int64 production_totale = 0;
for (const auto& rect : sources) {
if (côté_minimal == 0) return false;
production_totale += (rect.hauteur / côté_minimal) * (rect.largeur / côté_minimal);
if (production_totale >= nb_pieux_requis) return true;
}
return production_totale >= nb_pieux_requis;
}
int résoudre_maximisation_dimension(int nb_rectangles, Int64 quota_minimum, const std::vector<Dimension>& données) {
int gauche = 1, droite = 100000;
int meilleur_côté = 0;
while (gauche <= droite) {
int intermédiaire = gauche + (droite - gauche) / 2;
if (vérifier_quota(données, quota_minimum, intermédiaire)) {
meilleur_côté = intermédiaire;
gauche = intermédiaire + 1;
} else {
droite = intermédiaire - 1;
}
}
return meilleur_côté;
}
2. Pré-calcul Structuré pour Consultation Instantanée
Lorsque les requêtes portent sur des gammmes définies dans une séquence construite itérativement, la transformation en tableau de sommes partielles (préfixes) réduit la complexité de requête à O(1). Cette stratégie complète souvent une phase de recherche initiale.
#include <iostream>
#include <vector>
void générer_préfixes_et_interroger() {
int nombre_de_interrogations;
std::cin >> nombre_de_interrogations;
const int SEUIL_MAX = 10'000'000;
std::vector<int> séquence(SEUIL_MAX + 1);
int compteur = 0;
for (int niveau = 1; compteur <= SEUIL_MAX; ++niveau) {
for (int indice = 1; indice <= niveau && compteur <= SEUIL_MAX; ++indice) {
séquence[++compteur] = indice;
}
}
std::vector<int> accumulateur(compteur + 1, 0);
for (int i = 1; i <= compteur; ++i) {
accumulateur[i] = accumulateur[i - 1] + séquence[i];
}
for (int q = 0; q < nombre_de_interrogations; ++q) {
int indice_min, indice_max;
std::cin >> indice_min >> indice_max;
std::cout << (accumulateur[indice_max] - accumulateur[indice_min - 1]) << '\n';
}
}
3. Ajustement de Stock avec Réserves Partagées
Ce modèle traite l'équilibre de jeux complets lorsqu'on dispose d'un inventaire hétérogène et d'un pool de cartes vierges interchangeables. La validation vérifie si le déficit cumulé nécessaire pour atteindre un niveau X reste contenu dans le budget alloué.
#include <iostream>
#include <vector>
#include <algorithm>
using Int64 = long long;
bool vérifier_disponibilité_cartes(const std::vector<Int64>& stocks_en_cours,
const std::vector<Int64>& réserves_par_type,
Int64 budget_total_vierge, Int64 objectif_sets) {
Int64 vide_a_remplir = 0;
const size_t taille = stocks_en_cours.size();
for (size_t i = 0; i < taille; ++i) {
Int64 manque = objectif_sets - stocks_en_cours[i];
if (manque <= 0) continue;
if (manque > réserves_par_type[i]) return false;
vide_a_remplir += manque;
}
return vide_a_remplir <= budget_total_vierge;
}
Int64 calculer_nombre_max_de_sets(int nb_types, Int64 budget,
const std::vector<Int64>& possédés,
const std::vector<Int64>& blancs) {
Int64 borne_basse = 0, borne_haute = 0;
for (const auto& val : possédés) borne_haute = std::max(borne_haute, val);
borne_haute += budget;
while (borne_basse < borne_haute) {
Int64 candidat = borne_basse + (borne_haute - borne_basse + 1) / 2;
if (vérifier_disponibilité_cartes(possédés, blancs, budget, candidat)) {
borne_basse = candidat;
} else {
borne_haute = candidat - 1;
}
}
return borne_basse;
}
4. Minimisation du Facteur Critique Temporel
Appliqué à l'ordonnancement de unités mobiles cobayant une zone linéaire, l'objectif est de réduire la durée maximale enregistrée. En binarisant la distance de couverture par unité, on détermine la longueur minimale assurant une trajectoire continue sans trou non inspecté.
#include <iostream>
#include <vector>
#include <algorithm>
bool valider_couverture(int zone_totale, int nb_agents, const std::vector<int>& emplacements, int rayon_action) {
int dernier_point_balayé = 0;
for (int agent_idx = 0; agent_idx < nb_agents; ++agent_idx) {
if (emplacements[agent_idx] - rayon_action > dernier_point_balayé) {
return false; // Espace non recouvert détecté
}
if (dernier_point_balayé <= emplacements[agent_idx]) {
dernier_point_balayé += rayon_action;
} else {
dernier_point_balayé = emplacements[agent_idx] + rayon_action - 1;
}
}
return dernier_point_balayé >= zone_totale;
}
int calculer_temps_optimal(int taille_zone, int nb_opérateurs, const std::vector<int>& positions_initiales) {
std::vector<int> tri_positions(positions_initiale.begin(), position_initiale.end());
std::sort(tri_positions.begin(), tri_positions.end());
int minimum = 1, maximum = taille_zone;
while (minimum < maximum) {
int essai = minimum + (maximum - minimum) / 2;
if (valider_couverture(taille_zone, nb_opérateurs, tri_positions, essai)) {
maximum = essai;
} else {
minimum = essai + 1;
}
}
// Le temps effectif correspond au parcours aller-retour hors position de départ
return (minimum - 1) * 2;
}