Eerste True: binair zoeken op predicaat
Een monotone ja/nee-grens doorzoeken
Eerste True: binair zoeken op predicaat is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 3 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Zoek een ja/nee-grens
Veel problemen verbergen een monotoon predicaat: onwaar, onwaar en daarna altijd waar. Met binair zoeken kun je die eerste ware waarde vinden zonder een gesorteerde array.
# FFFFTTTT -> find first TWat monotoon betekent
Een predicaat is monotoon wanneer het waar blijft zodra het eenmaal waar is geworden. Dankzij die ene eigenschap kun je de grens binair zoeken.
def ok(x):
return x * x >= targetBaken de antwoordruimte af
Kies een bereik dat de grens zeker bevat. Stel low in op de kleinste kandidaat en high op een waarde waarvoor ok zeker waar is.
low, high = 0, 10**9Controleer het midden
Neem mid en roep ok(mid) aan. Het booleaanse resultaat vertelt je welke helft je moet behouden, precies zoals bij het vergelijken van een waarde tijdens gewoon binair zoeken.
mid = (low + high) // 2
if ok(mid):
...Waar betekent misschien kleiner
Als ok(mid) waar is, is mid een geldig antwoord, maar kan een kleinere waarde ook werken. Behoud mid door high = mid in te stellen, niet mid - 1.
if ok(mid):
high = midOnwaar betekent: ga hoger
Als ok(mid) onwaar is, ligt de grens boven mid. Gooi mid en alles eronder weg met low = mid + 1.
else:
low = mid + 1Herhaal zolang low kleiner is dan high
Gebruik while low < high, niet kleiner dan of gelijk aan. De twee pointers komen samen op de eerste ware index en daarna stopt de lus.
while low < high:
mid = (low + high) // 2Het antwoord is low
Wanneer de lus eindigt, zijn low en high gelijk en wijzen ze allebei naar de eerste ware waarde. Geef low terug als de grens die je zocht.
return low # first x where ok(x)Waarom high = mid werkt
Omdat mid het antwoord kan zijn, mag je het niet overslaan. Met high = mid houd je het binnen het bereik en verklein je dat toch, zodat je gegarandeerd vooruitgaat.
high = mid # mid stays a candidateVoorbeeld: gehele vierkantswortel
Als je de grootste x wilt vinden waarvoor x*x hoogstens n is, zoek je de eerste ware waarde van x*x > n en ga je daarna één stap terug. Het patroon is opnieuw bruikbaar.
def ok(x):
return x * x > n
# answer is found_index - 1Eén sjabloon, veel problemen
Dit sjabloon voor de eerste ware waarde lost talloze taken op: de minimale haalbare waarde, de meest linkse index en de kleinste capaciteit. Leer het één keer en gebruik het overal opnieuw.
# low<high, ok->high=mid, else low=mid+1Korte controle
Bepaal welke stap ervoor zorgt dat de kandidaat behouden blijft.
Samenvatting: de eerste ware waarde gevonden
Je kunt een probleem nu omzetten in een monotoon predicaat en de grens binair zoeken. high = mid met while low < high is het veilige patroon. 🧭
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Eerste True: binair zoeken op predicaat” gratis?
Ja — de volledige tekst van “Eerste True: binair zoeken op predicaat” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Eerste True: binair zoeken op predicaat”?
Een monotone ja/nee-grens doorzoeken Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 3 van 4.
Hoe lang duurt de les “Eerste True: binair zoeken op predicaat”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Klassiek binair zoeken zonder fouten
- bisect_left en bisect_right
- Eerste True: binair zoeken op predicaat
- Binair zoeken naar het antwoord