Premier True : recherche binaire par prédicat
Rechercher une frontière monotone oui/non
Premier True : recherche binaire par prédicat 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.
Recherchez une frontière oui/non
De nombreux problèmes cachent un prédicat monotone : faux, faux, puis toujours vrai. La recherche binaire peut trouver le premier vrai sans tableau trié.
# FFFFTTTT -> find first TCe que signifie monotone
Un prédicat est monotone lorsque, dès qu’il devient vrai, il le reste. C’est cette seule propriété qui permet de rechercher la frontière par dichotomie.
def ok(x):
return x * x >= targetDélimitez l’espace des réponses
Choisissez une plage qui contient certainement la frontière. Définissez low comme le plus petit candidat et high comme une valeur pour laquelle ok est certainement vrai.
low, high = 0, 10**9Testez le milieu
Prenez mid et appelez ok(mid). Le résultat booléen vous indique quelle moitié conserver, exactement comme lorsque vous comparez une valeur dans une recherche binaire classique.
mid = (low + high) // 2
if ok(mid):
...Vrai signifie peut-être plus petit
Si ok(mid) est vrai, mid est une réponse valide, mais une réponse plus petite peut aussi fonctionner. Conservez mid en définissant high = mid, et non mid - 1.
if ok(mid):
high = midFaux signifie aller plus haut
Si ok(mid) est faux, la frontière se trouve au-dessus de mid. Éliminez mid et tout ce qui est en dessous avec low = mid + 1.
else:
low = mid + 1Bouclez tant que low est inférieur à high
Utilisez while low < high, et non l’inférieur ou égal. Les deux pointeurs convergent vers le premier indice vrai, puis la boucle s’arrête.
while low < high:
mid = (low + high) // 2La réponse est low
Lorsque la boucle se termine, low est égal à high et tous deux pointent vers la première valeur vraie. Renvoyez low comme frontière recherchée.
return low # first x where ok(x)Pourquoi high = mid fonctionne
Comme mid peut être la réponse, vous ne devez pas l’ignorer. Utiliser high = mid le conserve dans la plage tout en la réduisant, ce qui garantit la progression.
high = mid # mid stays a candidateExemple de racine carrée entière
Pour trouver le plus grand x tel que x*x soit inférieur ou égal à n, recherchez le premier vrai de x*x > n, puis reculez d’un. Ce modèle se réutilise.
def ok(x):
return x * x > n
# answer is found_index - 1Un modèle, de nombreux problèmes
Ce modèle du premier vrai résout d’innombrables tâches : valeur minimale réalisable, indice le plus à gauche, capacité minimale. Apprenez-le une fois et réutilisez-le partout.
# low<high, ok->high=mid, else low=mid+1Vérification rapide
Identifiez le déplacement qui maintient le candidat en lice.
Récapitulatif : trouvez le premier vrai
Vous savez maintenant transformer un problème en prédicat monotone et rechercher sa frontière par dichotomie. high = mid, associé à while low < high, est le modèle sûr. 🧭
Questions Fréquemment Posées
La leçon « Premier True : recherche binaire par prédicat » est-elle gratuite ?
Oui — le texte complet de « Premier True : recherche binaire par prédicat » 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 « Premier True : recherche binaire par prédicat » ?
Rechercher une frontière monotone oui/non 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 « Premier True : recherche binaire par prédicat » ?
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 sans erreurs
- bisect_left et bisect_right
- Premier True : recherche binaire par prédicat
- Recherche binaire sur la réponse