Borne inférieure et borne supérieure
Implémentez bisect_left et bisect_right depuis zéro, puis utilisez-les pour trouver les première et dernière positions d’une valeur recherchée.
Borne inférieure et borne supérieure est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 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 Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Que sont les bornes inférieure et supérieure ?
La borne inférieure d’une valeur cible dans un tableau trié est l’indice du premier élément supérieur ou égal à la cible (souvent appelé bisect_left). La borne supérieure est l’indice du premier élément strictement supérieur à la cible (bisect_right). Ensemble, elles encadrent toutes les occurrences de la cible et permettent d’effectuer des requêtes sur des plages en O(log n).
Ces deux opérations constituent la base de nombreux problèmes d’entretien : compter les occurrences, trouver une plage, déterminer une position d’insertion, et bien plus encore.
arr = [1, 2, 2, 2, 3, 5]
# lower bound of 2 => index 1 (first element >= 2)
# upper bound of 2 => index 4 (first element > 2)
# occurrences of 2 => upper - lower = 4 - 1 = 3
print('lower bound of 2:', 1)
print('upper bound of 2:', 4)
print('count of 2:', 4 - 1)Implémenter la borne inférieure (bisect_left)
bisect_left(arr, x) renvoie le premier indice i tel que arr[i] >= x, ou len(arr) si tous les éléments sont plus petits. L’implémentation utilise une borne supérieure exclusive : hi = len(arr), une condition de boucle lo < hi, et met à jour hi = mid lorsque arr[mid] >= x. Cela garantit que la réponse converge vers la première position valide.
def bisect_left(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < x:
lo = mid + 1
else:
hi = mid # arr[mid] >= x, so potential answer
return lo # lo == hi == insertion point
arr = [1, 2, 2, 2, 3, 5]
print(bisect_left(arr, 2)) # 1
print(bisect_left(arr, 0)) # 0 (before all)
print(bisect_left(arr, 6)) # 6 (after all)
print(bisect_left(arr, 3)) # 4Implémenter la borne supérieure (bisect_right)
bisect_right(arr, x) renvoie le premier indice i tel que arr[i] > x. Une seule ligne diffère de bisect_left : la condition passe de arr[mid] < x à arr[mid] <= x. Lorsque arr[mid] <= x, la réponse se trouve strictement à droite de mid ; nous définissons donc lo = mid + 1. Sinon, nous resserrons la recherche par la droite.
def bisect_right(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= x:
lo = mid + 1 # arr[mid] <= x, so answer is strictly right
else:
hi = mid
return lo
arr = [1, 2, 2, 2, 3, 5]
print(bisect_right(arr, 2)) # 4
print(bisect_right(arr, 0)) # 0
print(bisect_right(arr, 5)) # 6
print(bisect_right(arr, 4)) # 5Compter les occurrences avec les deux bornes
Pour compter les occurrences d’une cible dans un tableau trié en O(log n), utilisez les deux bornes : le nombre d’occurrences est égal à bisect_right(arr, target) - bisect_left(arr, target). Si ce nombre vaut 0, la cible est absente. Cette méthode est nettement plus rapide qu’un parcours linéaire et constitue l’approche standard pour les requêtes de fréquence sur des données triées.
import bisect
def count_occurrences(arr, target):
left = bisect.bisect_left(arr, target)
right = bisect.bisect_right(arr, target)
return right - left
arr = [1, 2, 2, 2, 3, 3, 5]
print(count_occurrences(arr, 2)) # 3
print(count_occurrences(arr, 3)) # 2
print(count_occurrences(arr, 4)) # 0
print(count_occurrences(arr, 1)) # 1Trouver la première et la dernière position d’une cible
LeetCode 34, « Trouver la première et la dernière position d’un élément dans un tableau trié », vous demande de renvoyer [first_idx, last_idx] en O(log n). La première position est bisect_left(arr, target) — mais uniquement si arr[result] == target. La dernière position est bisect_right(arr, target) - 1. Si l’une ou l’autre vérification échoue, renvoyez [-1, -1].
import bisect
def search_range(nums, target):
left = bisect.bisect_left(nums, target)
if left == len(nums) or nums[left] != target:
return [-1, -1]
right = bisect.bisect_right(nums, target) - 1
return [left, right]
print(search_range([5,7,7,8,8,10], 8)) # [3, 4]
print(search_range([5,7,7,8,8,10], 6)) # [-1, -1]
print(search_range([], 0)) # [-1, -1]Position d’insertion (LeetCode 35)
LeetCode 35, « Rechercher la position d’insertion », demande : où faudrait-il insérer la cible pour conserver le tableau trié ? C’est exactement bisect_left(arr, target). Si la cible existe, bisect_left renvoie son indice. Si elle n’existe pas, bisect_left renvoie l’indice où elle serait insérée. Aucun traitement particulier n’est nécessaire : la même fonction gère les deux situations.
import bisect
def searchInsert(nums, target):
return bisect.bisect_left(nums, target)
print(searchInsert([1,3,5,6], 5)) # 2 (exists at index 2)
print(searchInsert([1,3,5,6], 2)) # 1 (would insert between 1 and 3)
print(searchInsert([1,3,5,6], 7)) # 4 (would append at end)
print(searchInsert([1,3,5,6], 0)) # 0 (would prepend)La différence entre bisect_left et bisect_right
Lorsqu’il n’y a pas de doublons, bisect_left et bisect_right renvoient le même indice. La différence n’a d’importance que lorsque la cible apparaît plusieurs fois. bisect_left pointe vers la première occurrence ; bisect_right pointe juste après la dernière occurrence. Choisissez toujours la fonction selon que vous souhaitez insérer avant les occurrences existantes (à gauche) ou après (à droite).
import bisect
arr = [1, 2, 2, 2, 3]
# Insert a new 2 before all existing 2s
print(bisect.bisect_left(arr, 2)) # 1
# Insert a new 2 after all existing 2s
print(bisect.bisect_right(arr, 2)) # 4
# For a value not in array, both give same insertion point
print(bisect.bisect_left(arr, 2.5)) # 4
print(bisect.bisect_right(arr, 2.5)) # 4Appliquer les bornes aux requêtes de fréquence sur des données triées
Lorsque vous devez répondre efficacement à de nombreuses requêtes de fréquence sur des plages dans un tableau trié, pré-calculer le tableau trié une seule fois, puis utilisez les bornes pour chaque requête. Chaque requête détermine « combien d’éléments se trouvent dans [lo, hi] ? » en O(log n) plutôt qu’en O(n). Ce schéma apparaît dans les problèmes qui consistent à compter les éléments appartenant à une plage de valeurs après un tri.
import bisect
def count_in_range(arr, lo, hi):
'''Count elements in arr with lo <= val <= hi. arr must be sorted.'''
left = bisect.bisect_left(arr, lo)
right = bisect.bisect_right(arr, hi)
return right - left
arr = sorted([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
print(arr) # [1,1,2,3,3,4,5,5,5,6,9]
print(count_in_range(arr, 3, 5)) # 6 (3,3,4,5,5,5)
print(count_in_range(arr, 1, 2)) # 3 (1,1,2)Recherche binaire avec clé personnalisée
Parfois, la clé de recherche n’est pas la valeur stockée elle-même, mais une propriété dérivée. Le module Python bisect ne prend pas directement en charge une fonction clé, mais vous pouvez effectuer vous-même une recherche binaire en appliquant la clé à l’intérieur de la boucle. Ce schéma est utile lorsque vous recherchez un élément dans une liste d’objets à partir de l’un de leurs attributs.
# Binary search on a list of (score, name) tuples by score
def lower_bound_by_score(records, min_score):
lo, hi = 0, len(records)
while lo < hi:
mid = lo + (hi - lo) // 2
if records[mid][0] < min_score:
lo = mid + 1
else:
hi = mid
return lo
records = [(50, 'Alice'), (72, 'Bob'), (72, 'Carol'), (88, 'Dave'), (95, 'Eve')]
idx = lower_bound_by_score(records, 72)
print(idx) # 1 (first record with score >= 72)
print(records[idx:]) # [(72,'Bob'),(72,'Carol'),(88,'Dave'),(95,'Eve')]Erreurs courantes en entretien concernant les bornes
L’erreur la plus courante consiste à oublier de valider le résultat après avoir appelé bisect_left. La fonction renvoie toujours un indice d’insertion valide, mais ne garantit pas que l’élément à cet indice est égal à la cible. Vérifiez toujours arr[result] == target avant de supposer que la cible a été trouvée.
Une deuxième erreur consiste à utiliser bisect_right lorsque vous recherchez la première occurrence : bisect_right renvoie la position juste après la dernière occurrence ; en soustrayant 1, vous obtenez donc la dernière, et non la première.
import bisect
arr = [1, 3, 5, 7]
target = 4
# bisect_left returns 2 (insertion point for 4 between 3 and 5)
idx = bisect.bisect_left(arr, target)
print(idx) # 2
# Validate: arr[2] is 5, not 4 => target absent
found = idx < len(arr) and arr[idx] == target
print('Found:', found) # FalseRésumé : quand utiliser bisect_left ou bisect_right
Utilisez bisect_left lorsque vous avez besoin de la première occurrence de la cible, du point d’insertion qui déplace les occurrences existantes vers la droite, ou de vérifier si la cible existe. Utilisez bisect_right lorsque vous avez besoin de la position juste après la dernière occurrence, du point d’insertion situé après toutes les occurrences existantes, ou du nombre d’éléments <= cible (il est égal à bisect_right(arr, target)).
Les deux opérations s’exécutent en O(log n) et font partie de la bibliothèque standard de Python ; vous pouvez donc les importer et les utiliser directement, sauf si la personne qui vous interroge vous demande de les implémenter à partir de zéro.
Vérification rapide
Évaluez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation abordés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris que : bisect_left trouve le premier élément >= cible, bisect_right trouve le premier élément > cible (juste après la dernière occurrence), et leur différence donne le nombre d’occurrences en O(log n). Ensuite, nous découvrirons la recherche binaire dans l’espace des réponses, où l’espace de recherche est une plage de réponses possibles, et non un indice de tableau.
Questions Fréquemment Posées
La leçon « Borne inférieure et borne supérieure » est-elle gratuite ?
Oui — le texte complet de « Borne inférieure et borne supérieure » 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 Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Borne inférieure et borne supérieure » ?
Implémentez bisect_left et bisect_right depuis zéro, puis utilisez-les pour trouver les première et dernière positions d’une valeur recherchée. Tu pratiques Coding 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 Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding 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 3 sur 4.
Combien de temps prend la leçon « Borne inférieure et borne supérieure » ?
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 Coding Interview Prep ?
Oui. Chaque leçon Coding 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