Förberedelse inför kodningsintervjuer · Lektion

Binärsökning på svaret

Gissa resultatet och kontrollera genomförbarheten

Lektion 4 av 413 steg

Binärsökning på svaret är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.

Gissa och verifiera

Ibland kan ni inte beräkna svaret direkt, men ni kan kontrollera en gissning. Binärsökning på svaret omvandlar svår optimering till enkel kontroll.

# guess X, ask: is X feasible?

Den avgörande egenskapen

Det fungerar när genomförbarheten är monoton: om ett värde fungerar, fungerar också alla större (eller mindre) värden. Det är den ordningen ni söker efter.

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

Avgränsa svarsintervallet

Identifiera de minsta och största möjliga svaren som low och high. För minsta kapacitet är low ett objekt och high den totala summan.

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

Skriv kontrollen av genomförbarhet

Metodens kärna är en can(X)-funktion som returnerar sant om gissningen X är möjlig. Den körs vanligtvis på linjär tid.

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

Exempel: Frakta på D dagar

Med den dagliga kapaciteten cap fyller ni dagarna girigt och räknar dem. can(cap) är sant när antalet dagar håller sig inom gränsen 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

Sök efter den minsta kapaciteten

Ni vill hitta den minsta cap som klarar kontrollen. Det är en sökning efter det första sanna värdet bland kapaciteter, så återanvänd mallen med high = mid.

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

Behåll den genomförbara halvan

Om can(mid) är sant kan en mindre kapacitet fortfarande fungera, så sätt high = mid. Annars höjer ni lägstanivån med low = mid + 1.

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

Tänk på tidsbudgeten

Den totala kostnaden är O(check x log range). En linjär kontroll över ett intervall på en miljard innebär bara omkring 30 kontroller, vilket är tillräckligt snabbt även med snäva gränser.

# log2(1e9) is about 30 iterations

Maximera i stället för att minimera

För att hitta det största genomförbara värdet vänder ni på logiken och söker efter det sista sanna värdet. Höj low när värdet är genomförbart och sänk high annars.

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

Svar med reella tal

För flyttalssvar kan ni i stället upprepa loopen ett fast antal gånger, till exempel 100, i stället för att använda ett heltals-mid. Varje omgång halverar intervallet och når mycket hög precision snabbt.

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

Upptäck mönstret

Uttryck som minsta största, största minsta eller minsta k som fungerar är signaler för att använda binärsökning på svaret. Träna er blick att upptäcka dem.

# 'minimize the maximum' => search answer

Snabb kontroll

Avgör när binärsökning på svaret passar.

Besvara frågan i den interaktiva lektionen

Sammanfattning: Sök efter svaret

Ni kan nu avgränsa svaret, skriva en genomförbarhetskontroll och använda binärsökning för att hitta minimum eller maximum. Svåra problem blir gissa och verifiera. 🏆

Gratis att börja

Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser: 90
Lektioner: 360

Börja lära dig gratis Visa hela kursen

Vanliga frågor

Är lektionen ”Binärsökning på svaret” gratis?

Ja – hela texten till ”Binärsökning på svaret” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.

Vad lär jag mig i ”Binärsökning på svaret”?

Gissa resultatet och kontrollera genomförbarheten Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?

Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.

Hur lång tid tar lektionen ”Binärsökning på svaret”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?

Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

← Tillbaka till Förberedelse inför kodningsintervjuer