6.2 Søking: sekvensielt søk og binærsøk

Lineært (sekvensielt) søk og iterativt binærsøk — hvordan de virker, forutsetningen om sortert liste, og å fylle inn/spore binærsøk-linjer.

45 min

7 oppgaver

Søkingsekvensielt søkbinærsøk

Din fremgang i kapitlet

0 / 7 oppgaver

Kapitlets plass i kurset

Bygger på

1.3Løkker — for, while og range

Brukes videre i

6.3Algoritmedefinisjon, pseudokode og kompleksitet (Big-O)

Dette kapitlet dekker to søkemetoder med svært ulik vekt på settet.

Sekvensielt søk er grunnstoff. Det får ingen egen prosent i arkivet, av den enkle grunnen at det aldri er en oppgave for seg selv — det er løkka som ligger under hver eneste analysefunksjon i programmeringsoppgaven. Og programmeringsoppgaven er der i alle 10 sittingene i arkivet (2014–2019), med 50–60 % av vekten. Hver gang du skal «finne raden der …», skriver du et sekvensielt søk uten å tenke på navnet.

Binærsøk er belagt i 3 av de 10 sittingene — omtrent 30 %. Det kommer i to former:

- Sjanger D — «fyll inn manglende kodelinje», altså et flervalg der én linje i en ferdig funksjon er byttet ut med en markør og du skal velge riktig linje. Binærsøk er favorittkandidaten, fordi de fire linjene som oppdaterer grensene, ser forvirrende like ut. Verdt 1–3 %.
- Som teori, der spørsmålet nesten alltid er det samme: hva forutsetter binærsøk? Svaret er at lista må være sortert.

Prioritet: sekvensielt søk må sitte (nivå 1), binærsøk bør du kjenne til (nivå 3, det laveste av bokas tre nivåer).

Ærlig prioritering: bruk de første 20 minuttene her på sekvensielt søk, og de neste 25 på binærsøk. Skal du velge bort noe fordi eksamen nærmer seg, er det å skrive binærsøk fra bunnen — men det å vite at det krever en sortert liste, koster deg ett minutt og kan gi et helt flervalgspoeng.

Forkunnskaper

- kap. 1.3 — løkker: for, while og range. Binærsøk er en while-løkke, så du bør være trygg på når en while stopper.
- kap. 3.1 — lister og indeksering.
- kap. 2.1 — funksjoner og return.
- kap. 6.1 — sortering. Binærsøk forutsetter en sortert liste, så de to kapitlene henger sammen.

En mykere inngang til det samme stoffet finnes i Søke- og sorteringsalgoritmer.

Har du aldri programmert: en indeks er plassnummeret til et element i ei liste, og det første elementet har indeks 0. Å returnere betyr at funksjonen gir en verdi tilbake til den som kalte den, og avslutter med det samme.

Løkke 1 — sekvensielt søk (~12 min)

Du leter etter én bestemt bok i en bunke som ligger i tilfeldig rekkefølge. Da finnes det bare én framgangsmåte: ta den øverste, sjekk om det er den rette, legg den fra deg, ta den neste. Er bunken tom uten at du fant boka, finnes den ikke der.

Det er sekvensielt søk, også kalt lineært søk. Det er ikke et triks — det er den åpenbare måten — men det er verdt å ha et navn på det, fordi resten av kapitlet handler om hva du kan gjøre bedre når bunken er sortert.

Sekvensielt søk

Et søk som går gjennom elementene ett om gangen, fra første til siste, og sammenligner hvert av dem med det du leter etter. Det stopper så snart det finner et treff. Metoden stiller ingen krav til rekkefølgen i lista — den virker like godt på en sortert og en usortert liste. Prisen er at du i verste fall må se på hvert eneste element. Det er formen du skriver i alle analysefunksjonene i programmeringsoppgaven.

`-1` som «ikke funnet»-verdi

Når en søkefunksjon skal gi tilbake en indeks, er -1 den avtalte verdien for «fantes ikke». Grunnen er at -1 aldri kan være en gyldig indeks i et treff: gyldige indekser er 0 og oppover. Skal funksjonen i stedet gi tilbake et element eller ei rad, bruker du None, og skal den gi tilbake flere treff, bruker du ei tom liste [] . Å håndtere «ikke funnet» er et av fullscore-kravene i emnet (feilkode #6) — en funksjon som bare krasjer, taper poeng.

`return` avslutter funksjonen straks

Så snart en return kjøres, hopper Python ut av funksjonen. Resten av løkka kjøres ikke. Det er nettopp derfor return i inne i løkka er riktig i et søk: du vil ha det første treffet, og du vil slutte å lete når du har det. Og det er derfor return -1 må stå etter løkka, ikke inne i den — står den inne, avbryter den etter første sammenligning som ikke traff.

📜Kodemønster: sekvensielt søk

Mønsteret er fem linjer, og de kommer alltid i denne rekkefølgen:

1. for i in range(len(x)): — gå gjennom alle lovlige indekser.
2. if x[i] == mal: — sammenlign elementet med det du leter etter.
3. return i — første treff, og ut av funksjonen med det samme.
4. Løkka slutter.
5. return -1 — kom du hit, fantes ikke verdien.

Den fjerde og femte linja er hele forskjellen på en funksjon som får full pott og en som krasjer på testdataene til sensor.

To faste varianter: skal du ha elementet i stedet for indeksen, går du gjennom for element in x og returnerer None til slutt. Skal du ha alle treffene, samler du dem i ei liste i stedet for å returnere ved første treff, og returnerer lista — som da er tom hvis ingen traff.

✏️Eksempel 1: finn plassen til et kønummer

En kølapp-liste inneholder nummerne i den rekkefølgen de ble trukket. Skriv finn_indeks(x, mal) som gir plassnummeret til mal, og -1 hvis nummeret ikke er trukket.

def finn_indeks(x, mal):
    for i in range(len(x)):
        if x[i] == mal:
            return i
    return -1

koer = [412, 907, 155, 660]
print(finn_indeks(koer, 155))
print(finn_indeks(koer, 300))

Utskrift:

2
-1

Første kall fant 155 på plass 2. Andre kall gikk gjennom hele lista uten treff, falt ut av løkka, og traff return -1.

Prøv å flytte return -1 inn i løkka, rett etter if-en, i hodet: da ville funksjonen returnert -1 allerede etter å ha sett på 412, uten å se på resten. Plasseringen er hele poenget.

📝Oppgave 1

(Innstegsoppgave, sjanger B — kodesporing, altså «hva skriver dette programmet ut?».) Funksjonen er den samme som i eksempel 1. Hva skriver programmet ut?

def finn_indeks(x, mal):
    for i in range(len(x)):
        if x[i] == mal:
            return i
    return -1

print(finn_indeks([7, 7, 3], 7))
print(finn_indeks([7, 7, 3], 9))

`v in x`

Gir True hvis verdien v finnes i lista x, ellers False . Negasjonen skrives v not in x . Dette er sekvensielt søk pakket inn i én operator: Python går gjennom lista for deg. Bruk den når du bare trenger å vite om verdien finnes. Trenger du å vite hvor den er, må du ha .index eller din egen løkke. in virker også på strenger ('ås' in tekst) og på nøklene i en ordbok.

`x.index(v)`

Gir indeksen til første forekomst av verdien v i lista. Finnes ikke verdien, kaster metoden ValueError og programmet stopper. Det er den viktige forskjellen fra din egen søkefunksjon: .index har ingen «ikke funnet»-verdi. Skal du bruke den trygt, må du sjekke først — if v in x: i = x.index(v) — eller pakke den i try/except . Skriver du din egen løkke med return -1, slipper du hele problemet.

`x.count(v)`

Gir antall ganger verdien v forekommer i lista, som et heltall. Finnes den ikke, gir metoden 0 — den krasjer aldri. Den er nyttig som en trygg forgjenger til .index : if x.count(v) > 0: . Men den går gjennom hele lista uansett, så bruk in når du bare vil ha ja eller nei.

✏️Eksempel 2: snarveiene, og der de ryker

Vis hva in, .index og .count gir på en liste med utlånte titler — og hva som skjer når du slår opp en tittel som ikke er utlånt.

De tre snarveiene, brukt trygt:

laan = ['Nordlys', 'Algoritmer', 'Vinterdagbok']
print('Algoritmer' in laan)
print(laan.index('Algoritmer'))
print('Kongens fall' in laan)
print(laan.count('Nordlys'))

Utskrift:

True
1
False
1

Og her er fella. .index på noe som ikke finnes, stopper programmet:

# tilsiktet feil: tittelen er ikke i lista, så .index stopper programmet
laan = ['Nordlys', 'Algoritmer', 'Vinterdagbok']
laan.index('Kongens fall')

Kodeblokken er merket som tilsiktet feilende. Siste linje i feilmeldingen er:

ValueError: 'Kongens fall' is not in list

Over den linja står noen linjer som viser hvor i koden det skjedde. Det er ValueError — den samme unntakstypen du møtte i kap. 4.3 — og den kan fanges med try/except, men det enkleste er å sjekke med in først.

Begge framgangsmåter gir full pott på eksamen — men de er trygge på ulike måter. if tittel in laan: foran .index er kort og lesbar. Din egen løkke med return -1 er like god, og den er den eneste av dem som fungerer når du søker i en 2D-tabell på én kolonne.

📝Oppgave 2

Sjanger B

Hva skriver programmet ut? Alle tre linjene.

hyller = ['A1', 'B2', 'A1', 'C3']
print('B2' in hyller)
print(hyller.index('A1'))
print(hyller.count('A1'))

Søk i en 2D-tabell

Sekvensielt søk i en tabell er den samme løkka, men med to tillegg: du finner kolonnen du skal sammenligne i, og du går bare gjennom dataradene. Formen er k = tabell[0].index(kolonnenavn), deretter for rad in tabell[1:]: og if rad[k] == verdi: return rad . Til slutt return None . Dette er den vanligste enkeltoppgaven i hele programmeringsdelen — «finn raden der \dots» — og den kombinerer søket med fullscore-kravet om å finne kolonnen dynamisk (feilkode #4).

✏️Eksempel 3: finn boka med et gitt ISBN

Bibliotekets bokliste har overskriftsraden ['tittel', 'isbn', 'hylle']. Skriv finn_rad(tabell, kolonnenavn, verdi) som gir hele raden der kolonnen har den oppgitte verdien, og None hvis ingen rad passer.

def finn_rad(tabell, kolonnenavn, verdi):
    k = tabell[0].index(kolonnenavn)
    for rad in tabell[1:]:
        if rad[k] == verdi:
            return rad
    return None

boker = [['tittel', 'isbn', 'hylle'],
         ['Nordlys', 9788203, 'A3'],
         ['Algoritmer', 9788205, 'B1'],
         ['Vinterdagbok', 9788241, 'A1']]
print(finn_rad(boker, 'isbn', 9788205))
print(finn_rad(boker, 'isbn', 1234567))

Utskrift:

['Algoritmer', 9788205, 'B1']
None

Tre grep gir uttelling her, og de er de samme hver gang:

- tabell[0].index(kolonnenavn) i stedet for et hardkodet 1-tall. Flytter noen på kolonnene i fila, virker koden fortsatt.
- tabell[1:] slik at overskriftsraden ikke kan gi et falskt treff.
- return None etter løkka — «ikke funnet» besvart, ikke krasjet.

Funksjonen er dessuten skrevet generelt: den tar kolonnenavnet inn som parameter, så den samme funksjonen finner boka på tittel like godt som på ISBN.

📝Oppgave 3

Eksamensnivå, sjanger G

Treningsloggen okter har overskriftsraden ['dato', 'aktivitet', 'minutter'].

a) Skriv okter_med(tabell, aktivitet) som returnerer ei liste med alle datoene der den oppgitte aktiviteten er logget. Returner ei tom liste hvis aktiviteten ikke finnes.
b) Forklar i én setning hvorfor funksjonen ikke trenger et eget tilfelle for «aktiviteten finnes ikke».

Løkke 2 — binærsøk (~25 min)

Dette delkapitlet er nivå 3 — «bør kjenne til». Det er belagt i 3 av 10 sittinger, og det du absolutt må ha med deg, er den ene setningen om forutsetningen. Resten er verdt å kunne, men ikke verdt å pugge foran Del 7.

Tenk på gjett-tallet-leken: en venn tenker på et tall mellom 1 og 100, og sier «høyere» eller «lavere» for hvert forsøk. Gjetter du 50 først, har du halvert mulighetene uansett hva svaret blir. Gjetter du 1 først, har du i praksis ikke lært noe.

Binærsøk er den strategien, brukt på ei sortert liste: se på midten, og kast bort halvparten. Det som gjør den mulig, er at et sortert element forteller noe om alle de andre — er tallet i midten for lite, kan målet umulig ligge til venstre for det.

Binærsøk

Et søk som gjentatte ganger ser på det midterste elementet i det gjenstående søkeområdet, og kaster den halvparten målet umulig kan ligge i. Forutsetningen er at lista er sortert. Er den ikke det, gir binærsøk gale svar — uten feilmelding. Til gjengjeld er det svært raskt: hvert steg halverer området som er igjen, så ei liste med en million elementer er gjennomsøkt på 20 steg.

Forutsetningen: lista må være sortert

Binærsøk bygger på at når x[imid] er mindre enn målet, så er alt til venstre for imid også mindre. Den slutningen holder bare i ei sortert liste. Dette er det oftest testede punktet om binærsøk på eksamen, og det farlige er at koden ikke krasjer på usortert inndata: den returnerer bare -1 eller feil indeks. Skal du søke i noe usortert, har du to valg — sorter først (kap. 6.1), eller bruk sekvensielt søk.

Søkevinduet `imin` og `imax`

De to variablene holder styr på hvilken del av lista som fortsatt kan inneholde målet: fra og med indeks imin til og med indeks imax . De starter på 0 og len(x) - 1, altså hele lista. For hvert steg flyttes den ene av dem innover, og vinduet krymper. Skjærer de forbi hverandre — imin blir større enn imax — er vinduet tomt, og målet finnes ikke.

`imid = (imin + imax) // 2`

Midten av søkevinduet. Dobbel skråstrek er heltallsdeling, som runder nedover — nødvendig fordi en indeks må være et helt tall. Vanlig deling med / gir et flyttall og dermed TypeError når du prøver å indeksere med det. Med imin = 4 og imax = 6 gir formelen 10 // 2, altså 5. Med imin = 4 og imax = 5 gir den 9 // 2, altså 4 — den runder ned mot venstre. Denne linja er den vanligste kandidaten for «fyll inn manglende kodelinje».

`while imin <= imax`

Løkka kjører så lenge søkevinduet har minst ett element igjen. Likhetstegnet er nødvendig: når imin og imax er like, er det nøyaktig ett element igjen — og det kan godt være det du leter etter. Skriver du < i stedet for <=, hopper søket over det siste elementet i vinduet og returnerer -1 for verdier som faktisk finnes. Det er en stille feil som bare rammer noen av oppslagene, og derfor lett å overse.

`imin = imid + 1`

Steget som brukes når x[imid] er mindre enn målet: hele venstre halvdel, inkludert midtelementet, kastes. + 1 er ikke pynt. Uten det blir imin stående lik imid, vinduet krymper ikke, og løkka går for alltid — programmet henger. Midtelementet kan trygt kastes, siden du nettopp har sjekket at det ikke er treff.

`imax = imid - 1`

Speilbildet: brukes når x[imid] er større enn målet, og kaster hele høyre halvdel inkludert midtelementet. Også her er - 1 det som garanterer at vinduet krymper. Merk at imax godt kan bli -1 : skjer det, er imin (som er 0) større enn imax, løkka stopper, og funksjonen returnerer -1 for «ikke funnet».

Halvering av søkerommet

\log_2 n

📜Kodemønster: iterativt binærsøk

Ordet iterativ betyr «med løkke», til forskjell fra rekursiv, der funksjonen kaller seg selv. Løkkeversjonen er den arkivets oppgaver bruker.

Seks steg, i denne rekkefølgen:

1. imin = 0 og imax = len(x) - 1 — vinduet er hele lista.
2. while imin <= imax: — så lenge vinduet ikke er tomt.
3. imid = (imin + imax) // 2 — finn midten.
4. if x[imid] == mal: return imid — treff, og ut.
5. elif x[imid] < mal: imin = imid + 1 — målet må ligge til høyre.
6. else: imax = imid - 1 — målet må ligge til venstre. Etter løkka: return -1.

Tre av de seks linjene er kandidater for «fyll inn manglende kodelinje». Lær deg å resonnere deg fram til dem i stedet for å pugge: er midten for liten, må du lete til høyre, altså flytte den nedre grensen opp forbi midten.

✏️Eksempel 4: binærsøk med sporingstavle

Lista [104, 211, 317, 428, 530, 646, 752] er sortert. Skriv et iterativt binærsøk, og spor det for verdien 530 og for verdien 400, som ikke finnes.

def binaersok(x, mal):
    imin = 0
    imax = len(x) - 1
    while imin <= imax:
        imid = (imin + imax) // 2
        if x[imid] == mal:
            return imid
        elif x[imid] < mal:
            imin = imid + 1
        else:
            imax = imid - 1
    return -1

sortert = [104, 211, 317, 428, 530, 646, 752]
print(binaersok(sortert, 530))
print(binaersok(sortert, 104))
print(binaersok(sortert, 400))

Utskrift:

4
0
-1

Sporing av søket etter 530 — tre steg på ei liste med sju elementer:

Steg	`imin`	`imax`	`imid`	`x[imid]`	Hva skjer
1	0	6	3	`428`	`428 < 530` $\to$ søk til høyre, `imin = 4`
2	4	6	5	`646`	`646 > 530` $\to$ søk til venstre, `imax = 4`
3	4	4	4	`530`	`530 == 530` $\to$ funnet, returnerer `4`

Sporing av søket etter 400, som ikke finnes. Her er poenget hvordan løkka stopper:

Steg	`imin`	`imax`	`imid`	`x[imid]`	Hva skjer
1	0	6	3	`428`	`428 > 400` $\to$ søk til venstre, `imax = 2`
2	0	2	1	`211`	`211 < 400` $\to$ søk til høyre, `imin = 2`
3	2	2	2	`317`	`317 < 400` $\to$ søk til høyre, `imin = 3`
4	3	2	—	—	`imin > imax` $\to$ vinduet er tomt, returnerer `-1`

Legg merke til den siste raden: imin passerte imax, betingelsen imin <= imax ble usann, og programmet falt ut av løkka til return -1. Det er slik binærsøk avslutter når verdien ikke finnes — ikke ved å ha sett på alle elementene, men ved at vinduet er krympet til ingenting.

Typiske feil: binærsøk

Fire feil, og alle fire er belagt som fellene sjanger D bygger på:

- Å glemme + 1 eller - 1 på grensene. Skriver du imin = imid, krymper ikke vinduet når midten er den nedre grensen, og løkka går for alltid. Programmet henger — det er ikke engang en feilmelding å lete etter.
- < i stedet for <= i while-betingelsen. Da hopper søket over det siste elementet i vinduet, og du får -1 for verdier som finnes.
- Å bruke binærsøk på ei usortert liste. Ingen feilmelding, bare feil svar. Dette er feilkode #5 i sin farligste form: koden ser riktig ut og kjører fint.
- / i stedet for //. (imin + imax) / 2 gir et flyttall, og x[3.0] gir TypeError: list indices must be integers or slices, not float.

Motgiften er den samme for alle fire: spor søket for hånd på ei liste med fem–sju elementer, både for en verdi som finnes og for en som ikke gjør det. Går den siste sporingen i evig løkke, har du en av de to første feilene.

✏️Eksempel 5: den stille feilen på usortert liste

Vis hva det samme binærsøket gir når lista ikke er sortert.

Lista under inneholder 211 — på plass 3. Binærsøket finner den ikke:

def binaersok(x, mal):
    imin = 0
    imax = len(x) - 1
    while imin <= imax:
        imid = (imin + imax) // 2
        if x[imid] == mal:
            return imid
        elif x[imid] < mal:
            imin = imid + 1
        else:
            imax = imid - 1
    return -1

usortert = [530, 104, 752, 211]
print(usortert.index(211))
print(binaersok(usortert, 211))

Utskrift:

3
-1

Første linje viser sannheten: 211 står på plass 3. Andre linje er binærsøkets svar: -1, altså «finnes ikke».

Hva gikk galt? Midten var x[1], altså 104. Siden 104 er mindre enn 211, konkluderte søket med at 211 må ligge til høyre — og kastet plass 0. Neste midt var 752, som er større, så nå ble alt til høyre kastet, inkludert plass 3 der 211 faktisk lå. Slutningen «alt til venstre for et for lite tall er også for lite» er sann i ei sortert liste og usann her.

Ingen feilmelding kom. Det er derfor forutsetningen er det eneste du absolutt må huske om binærsøk.

📝Oppgave 4

Eksamensnivå, sjanger D

Funksjonen skal søke i ei sortert liste. Linja #KODE1 skal oppdatere grensen når det midterste elementet er mindre enn det du leter etter.

def binaersok(x, mal):
    imin = 0
    imax = len(x) - 1
    while imin <= imax:
        imid = (imin + imax) // 2
        if x[imid] == mal:
            return imid
        elif x[imid] < mal:
            #KODE1
        else:
            imax = imid - 1
    return -1

Hvilken linje hører hjemme på #KODE1?

1. imin = imid + 1
2. imin = imid
3. imax = imid - 1
4. imin = imid - 1

📝Oppgave 5

Eksamensnivå, sjanger J

Lista [3, 8, 12, 19, 25, 31] er sortert. Sett opp en sporingstavle for binaersok(x, 25) med kolonnene imin, imax, imid og x[imid], og oppgi hva funksjonen returnerer. Funksjonen er den fra eksempel 4.

📝Oppgave 6

Eksamensnivå, sjanger J

Bibliotekets ISBN-register numre er ei liste med heltall.

a) Skriv sok_isbn(numre, isbn) som bruker binærsøk og returnerer indeksen, eller -1 hvis nummeret ikke finnes.
b) Registeret kommer usortert fra fila. Skriv sok_isbn_trygt(numre, isbn) som virker uansett rekkefølge — uten å endre lista den fikk inn.
c) Forklar i én setning hvorfor b) likevel kan være dårligere enn et sekvensielt søk når du bare skal slå opp ett nummer.

Duplikater: hvilken indeks får du?

Sekvensielt søk gir alltid første forekomst, fordi det går fra venstre og returnerer ved første treff. Binærsøk gir en vilkårlig forekomst — den det tilfeldigvis lander på. I lista [3, 5, 5, 5, 9] gir sekvensielt søk etter 5 indeks 1, mens binærsøk gir indeks 2. Begge er «riktige» treff, men de er ikke like. Ber oppgaven om den første forekomsten, kan du ikke bruke binærsøk uten videre.

✏️Eksempel 6: to søk, to svar

Vis at sekvensielt søk og binærsøk gir ulik indeks når verdien finnes flere ganger.

def finn_indeks(x, mal):
    for i in range(len(x)):
        if x[i] == mal:
            return i
    return -1

def binaersok(x, mal):
    imin = 0
    imax = len(x) - 1
    while imin <= imax:
        imid = (imin + imax) // 2
        if x[imid] == mal:
            return imid
        elif x[imid] < mal:
            imin = imid + 1
        else:
            imax = imid - 1
    return -1

tall = [3, 5, 5, 5, 9]
print(finn_indeks(tall, 5))
print(binaersok(tall, 5))

Utskrift:

1
2

Begge svarene peker på et femtall, så begge er treff. Men bare det første er «den første forekomsten».

Binærsøket landet på indeks 2 fordi (0 + 4) // 2 er 2, og der lå det tilfeldigvis et femtall — det sluttet å lete med en gang. Står det «første forekomst» i oppgaveteksten, er sekvensielt søk det trygge valget.

📝Oppgave 7

Sjanger C

Skriv én presis setning om hva funksjonen oppnår. Setningen skal si hva den gir tilbake, ikke hvordan den regner.

def ukjent(x, mal):
    imin = 0
    imax = len(x) - 1
    while imin <= imax:
        imid = (imin + imax) // 2
        if x[imid] == mal:
            return imid
        elif x[imid] < mal:
            imin = imid + 1
        else:
            imax = imid - 1
    return -1

Når velger du hva?

Tre spørsmål avgjør, i denne rekkefølgen:

1. Er lista sortert? Er den ikke det, og du ikke skal sortere den uansett: sekvensielt søk.
2. Skal du slå opp én gang eller mange? Ett oppslag i ei usortert liste er alltid sekvensielt søk — å sortere først koster mer enn det sparer. Mange oppslag i den samme lista: sorter én gang, og bruk binærsøk etterpå.
3. Trenger du den første forekomsten, alle forekomstene, eller bare ett treff? Bare sekvensielt søk gir deg de to første på en enkel måte.

På eksamen er svaret nesten alltid sekvensielt søk, fordi oppgavene arbeider på tabeller lest fra fil i vilkårlig rekkefølge. Binærsøk kommer når oppgaven sier at lista er sortert — det er signalordet du skal se etter.

Bør kjenne til — rekursivt binærsøk

API- og konstruksjonsliste

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.