Recherche binaire dans l’espace des réponses
Traitez un intervalle continu de réponses comme un espace de recherche pour résoudre des problèmes tels que minimum-time-to-complete-jobs et capacity-to-ship-packages.
Recherche binaire dans l’espace des réponses est une leçon DSA Interview Prep 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 DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Recherche binaire dans l’espace des réponses
La plupart des gens connaissent la recherche binaire pour trouver une valeur dans un tableau trié. Mais la recherche binaire est encore plus puissante lorsqu’elle s’applique à l’espace des réponses possibles. Au lieu de rechercher dans un tableau, vous recherchez dans une plage numérique — par exemple : « quel est le nombre minimal de jours nécessaires pour expédier tous les colis ? » — et utilisez une fonction de vérification pour déterminer si une réponse candidate est réalisable.
Cette technique transforme de nombreux problèmes d’optimisation de O(n²) ou pire en O(n log(max_answer)).
Le modèle de l’espace des réponses
Le modèle comporte trois éléments. Premièrement, définissez la plage de recherche [lo, hi] qui encadre toutes les réponses valides. Deuxièmement, écrivez une vérification de faisabilité can_achieve(mid) qui renvoie une valeur vraie si la valeur mid est réalisable. Troisièmement, effectuez une recherche binaire sur [lo, hi] : si can_achieve(mid) renvoie vrai, avancez vers une réponse plus petite (ou plus grande) ; sinon, déplacez-vous dans l’autre direction.
La propriété essentielle est que la fonction de faisabilité doit être monotone : dès qu’une réponse est réalisable, toutes les valeurs au-delà le sont également (ou toutes les valeurs en dessous sont irréalisables).
# Generic template
def answer_space_search(lo, hi, is_feasible):
result = hi # or lo, depending on direction
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
hi = mid - 1 # try to minimise further
else:
lo = mid + 1
return resultExemple : capacité d’expédition des colis
LeetCode 1011 « Capacité d’expédition des colis dans un délai de D jours » : étant donné une liste de poids et D jours, trouvez la capacité d’expédition minimale permettant d’expédier tous les colis dans l’ordre en D jours. La réponse se trouve dans [max(weights), sum(weights)]. Une capacité est réalisable si une simulation gloutonne permet de faire tenir tous les colis dans D jours. Une recherche binaire sur l’intervalle des capacités donne une complexité temporelle en O(n log(somme)).
def shipWithinDays(weights, days):
def can_ship(capacity):
needed_days, current_load = 1, 0
for w in weights:
if current_load + w > capacity:
needed_days += 1
current_load = 0
current_load += w
return needed_days <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_ship(mid):
hi = mid # feasible, try smaller
else:
lo = mid + 1 # not feasible, need more capacity
return lo
print(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5)) # 15
print(shipWithinDays([3,2,2,4,1,4], 3)) # 6Exemple : Koko mange des bananes
LeetCode 875 « Koko mange des bananes » : Koko peut manger K bananes par heure ; elle veut terminer H tas en exactement H heures, en minimisant K. L’intervalle de recherche est [1, max(piles)]. La vérification est la suivante : au débit K, le nombre total d’heures = sum(ceil(tas/K)), et ce nombre doit être <= H. Nous effectuons une recherche binaire pour trouver le plus petit K qui respecte cette condition.
import math
def minEatingSpeed(piles, h):
def can_finish(k):
return sum(math.ceil(p / k) for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_finish(mid):
hi = mid # feasible, try lower speed
else:
lo = mid + 1 # too slow
return lo
print(minEatingSpeed([3,6,7,11], 8)) # 4
print(minEatingSpeed([30,11,23,4,20], 5)) # 30Exemple : nombre minimal de jours pour confectionner des bouquets
LeetCode 1482 « Nombre minimal de jours pour confectionner m bouquets » : vous avez besoin de m bouquets, chacun composé de k fleurs écloses consécutives. La fleur i éclot le jour bloomDay[i]. Effectuez une recherche binaire sur le jour : l’intervalle va de 1 à la valeur maximale de bloomDay. La vérification de faisabilité compte les fleurs écloses consécutives et détermine si m bouquets peuvent être formés. Propriété de monotonie : si le jour d convient, le jour d+1 convient également.
def minDays(bloomDay, m, k):
if m * k > len(bloomDay):
return -1 # impossible
def can_make(day):
bouquets = consecutive = 0
for bd in bloomDay:
if bd <= day:
consecutive += 1
if consecutive == k:
bouquets += 1
consecutive = 0
else:
consecutive = 0
return bouquets >= m
lo, hi = 1, max(bloomDay)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_make(mid):
hi = mid
else:
lo = mid + 1
return lo
print(minDays([1,10,3,10,2], 3, 1)) # 3
print(minDays([1,10,3,10,2], 3, 2)) # -1Déterminer l’intervalle de recherche
Choisir le bon intervalle [borne inférieure, borne supérieure] est essentiel. lo doit être la réponse minimale possible (par exemple, le plus petit élément, 1 ou 0) et hi doit être la réponse maximale possible (par exemple, la somme de tous les éléments, l’élément maximal ou n). Une borne supérieure trop petite exclut des réponses valides ; une borne supérieure trop grande ne pose aucun problème, car la recherche binaire convergera tout de même en O(log(hi - lo)) étapes.
# Choosing lo and hi for common problems:
# Capacity to ship: lo=max(weights), hi=sum(weights)
# Koko eating: lo=1, hi=max(piles)
# Square root: lo=1, hi=x
# Allocate books: lo=max(pages), hi=sum(pages)
def isqrt_bs(x):
if x < 2:
return x
lo, hi = 1, x
while lo < hi:
mid = lo + (hi - lo) // 2
if mid * mid <= x:
lo = mid + 1
else:
hi = mid
return lo - 1
for n in [0, 1, 4, 8, 9, 15, 16]:
print(f'isqrt({n}) = {isqrt_bs(n)}')Maximiser ou minimiser : le sens compte
La recherche binaire dans l’espace des réponses a deux variantes. Minimiser la réponse : lorsque la vérification réussit, essayez une valeur plus petite (hi = mid) ; lorsqu’elle échoue, essayez une valeur plus grande (lo = mid + 1). Maximiser la réponse : lorsque la vérification réussit, essayez une valeur plus grande (lo = mid + 1, en conservant la valeur médiane comme candidate) ; lorsqu’elle échoue, essayez une valeur plus petite (hi = mid - 1). Clarifiez toujours le sens de la recherche avant de coder.
# Maximise: largest x such that f(x) is feasible
def max_feasible(lo, hi, is_feasible):
result = lo - 1 # sentinel: no feasible answer found
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
lo = mid + 1 # try larger
else:
hi = mid - 1
return result
# Example: largest k such that k^2 <= 50
print(max_feasible(1, 50, lambda k: k * k <= 50)) # 7Allocation minimale de pages (problème classique)
Étant donné n livres, dont les nombres de pages sont stockés dans un tableau, et k étudiants, répartissez les livres de manière contiguë afin que l’étudiant qui lit le plus de pages en lise le moins possible. Effectuez une recherche binaire sur la réponse (le maximum minimal possible). La vérification de faisabilité attribue gloutonnement les livres aux étudiants : lorsqu’ajouter un livre dépasserait le maximum actuel, attribuez-le à un nouvel étudiant. Si le nombre d’étudiants nécessaires est <= k, ce maximum est réalisable.
def allocate_min_pages(pages, k):
if k > len(pages):
return -1
def is_feasible(max_pages):
students, current = 1, 0
for p in pages:
if p > max_pages:
return False # single book exceeds limit
if current + p > max_pages:
students += 1
current = 0
current += p
return students <= k
lo, hi = max(pages), sum(pages)
while lo < hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
print(allocate_min_pages([12, 34, 67, 90], 2)) # 113
print(allocate_min_pages([10, 20, 30, 40], 2)) # 60Analyse de la complexité de la recherche dans l’espace des réponses
La complexité temporelle est O(n × log(intervalle)), où n est le coût de la vérification de faisabilité (généralement un parcours linéaire) et où l’intervalle correspond à la taille de l’espace des réponses. Par exemple, si la somme des pages vaut 10⁹ et que la vérification de faisabilité est en O(n), le temps total est O(n log 10⁹) ≈ O(30n), ce qui est bien meilleur qu’une recherche exhaustive en O(n²).
La complexité spatiale est O(1) pour la recherche binaire elle-même, à laquelle s’ajoute l’espace utilisé par la vérification de faisabilité.
import math
# Compare brute force vs answer-space binary search
# For sum = 10^9 and n = 10^5:
brute_ops = 10**9 # try every possible answer
bsearch_ops = 10**5 * math.log2(10**9) # n * log(range)
print(f'Brute force: {brute_ops:,.0f} operations')
print(f'Binary search: {bsearch_ops:,.0f} operations')
print(f'Speedup: {brute_ops / bsearch_ops:,.0f}x')K-ième plus petite valeur dans une matrice triée
LeetCode 378 « K-ième plus petite valeur dans une matrice triée » : chaque ligne et chaque colonne d’une matrice n×n est triée. Effectuez une recherche binaire sur la valeur de réponse dans l’intervalle allant de la valeur en haut à gauche de la matrice à celle en bas à droite. La vérification de faisabilité compte les éléments <= mid à l’aide d’un pointeur partant du coin inférieur gauche, en O(n). Trouvez la plus petite valeur pour laquelle au moins k éléments sont <= mid.
def kthSmallest(matrix, k):
n = len(matrix)
def count_le(mid):
count, row, col = 0, n - 1, 0
while row >= 0 and col < n:
if matrix[row][col] <= mid:
count += row + 1
col += 1
else:
row -= 1
return count
lo, hi = matrix[0][0], matrix[n-1][n-1]
while lo < hi:
mid = lo + (hi - lo) // 2
if count_le(mid) >= k:
hi = mid
else:
lo = mid + 1
return lo
matrix = [[1,5,9],[10,11,13],[12,13,15]]
print(kthSmallest(matrix, 8)) # 13Reconnaître les problèmes de recherche dans l’espace des réponses
Les problèmes adaptés à la recherche binaire dans l’espace des réponses présentent plusieurs signaux courants : la question demande une valeur minimale ou maximale, la réponse se trouve dans un intervalle numérique borné, et augmenter (ou diminuer) la réponse candidate améliore ou dégrade la faisabilité de manière monotone. Parmi les formulations classiques figurent « maximum minimal possible », « au plus k opérations » et « en d jours ».
Lorsque vous repérez ces signaux, définissez immédiatement les bornes inférieure et supérieure, écrivez la fonction de faisabilité et appliquez le modèle. Cette approche structurée échoue rarement lors des entretiens.
Vérification rapide
Évaluez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris que : la recherche binaire dans l’espace des réponses s’applique lorsqu’une fonction de faisabilité est monotone sur un intervalle numérique, le modèle effectue une recherche dans [borne inférieure, borne supérieure] et utilise une vérification de faisabilité pour diviser l’espace de recherche par deux, et la complexité totale est O(n log(intervalle)), où n est le coût d’une vérification de faisabilité. Nous allons maintenant passer aux listes chaînées et à la classe Nœud.
Questions Fréquemment Posées
La leçon « Recherche binaire dans l’espace des réponses » est-elle gratuite ?
Oui — le texte complet de « Recherche binaire dans l’espace des réponses » 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 DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Recherche binaire dans l’espace des réponses » ?
Traitez un intervalle continu de réponses comme un espace de recherche pour résoudre des problèmes tels que minimum-time-to-complete-jobs et capacity-to-ship-packages. Tu pratiques DSA Interview Prep 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 DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep 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 dans l’espace des réponses » ?
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 DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep 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
- Recherche binaire classique : gauche, droite, milieu
- Recherche binaire dans des tableaux pivotés et non triés
- Borne inférieure et borne supérieure
- Recherche binaire dans l’espace des réponses