0Pricing
Competitive Programming Academy · Leçon

Recherche binaire sur la réponse

Deviner le résultat et vérifier sa faisabilité

Recherche binaire sur la réponse est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.

Devinez, puis vérifiez

Parfois, vous ne pouvez pas calculer directement la réponse, mais vous pouvez vérifier une hypothèse. La recherche binaire sur la réponse transforme une optimisation difficile en vérification simple.

# guess X, ask: is X feasible?

La propriété magique

Cette méthode fonctionne lorsque la faisabilité est monotone : si une valeur fonctionne, toute valeur plus grande (ou plus petite) fonctionne également. C’est cet ordre que vous recherchez.

# feasible(X) true => feasible(X+1) true

Encadrez la plage de réponses

Identifiez les plus petite et plus grande réponses possibles comme low et high. Pour une capacité minimale, low vaut un élément et high la somme totale.

low, high = max(weights), sum(weights)

Écrivez la vérification de faisabilité

Le cœur de la méthode est une fonction can(X) qui renvoie vrai si l’hypothèse X est réalisable. Elle s’exécute généralement en temps linéaire.

def can(cap):
    # simulate and return True/False
    ...

Exemple : expédier en D jours

Étant donné une capacité quotidienne cap, remplissez gloutonnement les jours et comptez-les. can(cap) est vrai lorsque le nombre de jours reste dans la limite D.

def can(cap):
    days, load = 1, 0
    for w in weights:
        if load + w > cap:
            days += 1; load = 0
        load += w
    return days <= D

Recherchez la capacité minimale

Vous voulez la plus petite cap qui réussit. C’est une recherche du premier vrai parmi les capacités, alors réutilisez le modèle high = mid.

while low < high:
    mid = (low + high) // 2

Conservez la moitié réalisable

Si can(mid) est vrai, une capacité plus petite peut encore fonctionner, alors définissez high = mid. Sinon, relevez la limite inférieure avec low = mid + 1.

if can(mid):
    high = mid
else:
    low = mid + 1

Surveillez le budget temps

Le coût total est O(coût de la vérification × log(plage)). Une vérification linéaire sur une plage d’un milliard de valeurs ne demande qu’environ 30 vérifications, ce qui est assez rapide pour des limites strictes.

# log2(1e9) is about 30 iterations

Maximisez plutôt que minimisez

Pour trouver la plus grande valeur réalisable, inversez la logique : recherchez le dernier vrai. Augmentez low lorsque c’est faisable et réduisez high dans le cas contraire.

if can(mid):
    low = mid
else:
    high = mid - 1

Réponses à valeurs réelles

Pour les réponses à virgule flottante, effectuez une boucle avec un nombre fixe d’itérations, par exemple 100, au lieu de calculer un milieu entier. Chaque tour divise l’intervalle par deux et atteint rapidement une précision infime.

for _ in range(100):
    mid = (low + high) / 2

Repérez le modèle

Des expressions comme minimum du maximum, maximum du minimum ou plus petit k qui fonctionne sont des signaux indiquant qu’il faut appliquer une recherche binaire à la réponse. Habituez votre regard à les repérer.

# 'minimize the maximum' => search answer

Vérification rapide

Déterminez quand appliquer la recherche binaire à la réponse.

Récapitulatif : recherchez la réponse

Vous savez maintenant encadrer la réponse, écrire une vérification de faisabilité et effectuer une recherche binaire du minimum ou du maximum. Les problèmes difficiles deviennent des exercices de conjecture et de vérification. 🏆

Questions Fréquemment Posées

La leçon « Recherche binaire sur la réponse » est-elle gratuite ?

Oui — le texte complet de « Recherche binaire sur la réponse » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Recherche binaire sur la réponse » ?

Deviner le résultat et vérifier sa faisabilité Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?

Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.

Combien de temps prend la leçon « Recherche binaire sur la réponse » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?

Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Recherche binaire classique sans erreurs
  2. bisect_left et bisect_right
  3. Premier True : recherche binaire par prédicat
  4. Recherche binaire sur la réponse
← Retour à Competitive Programming Academy