3.4 Søk i pseudokode — binærsøk, finn duplikat og finn par

De faste Del 2-søkeoppgavene: modifisert binærsøk til indeks, finn duplikat, og finn par som summerer til x — der valget mellom hash og sortering avgjør poengtrappen.

55 min

6 oppgaver

Søk i pseudokodebinærsøkfinn duplikatfinn par

Din fremgang i kapitlet

0 / 6 oppgaver

Kapitlets plass i kurset

Bygger på

3.2Load-faktor, rehashing og hashmap/-set som verktøy

Brukes videre i

3.PPrøver til del 3: Hashing og søk

Dette er et Del 2-kapittel, altså den delen av eksamen der du skriver
pseudokode og resonnerer, og der karakteren avgjøres.

Sjanger I — hashing og søk i pseudokode har vært på så godt som alle sju
settene. De tre oppgavetypene som går igjen er nøyaktig de tre dette kapitlet
dekker: modifisert binærsøk, finn duplikat og finn par som summerer til
$x$ .

Det som gjør kapitlet spesielt, er at poengtrappen er eksplisitt her.
Sensorveiledningene sier rett ut at lavere kjøretid gir mer uttelling på samme
oppgave: en $O(n)$ -løsning gir full pott, $O(n \log n)$ gir noe mindre, og en
dobbel løkke på $O(n^2)$ gir minst. Alle tre er korrekte. Å velge riktig
verktøy er å velge poeng.

Én fast trekkgrunn er verdt å kjenne på forhånd: pensums binærsøk returnerer
sant eller usant, ikke en indeks. Hevder du at det returnerer en indeks uten å
nevne at det må modifiseres, trekkes det. Det er felle #4 i bokas
feilregister.

Prioritet: høyeste. Dette er de billigste Del 2-poengene i hele faget, fordi
algoritmene er korte og mønstrene gjentar seg.

Slik er kapitlet lagt opp (55 min): fire løkker med tidsanslag og et
pausepunkt underveis.

Forkunnskaper

- kap. 3.2 — hash-set og hashmap, og hvorfor de gir $O(n)$
forventet. Halvparten av kapitlet hviler på det.
- kap. 2.2 — sortér-og-skann-strategien og
$O(n \log n)$ -sorteringene, som er alternativet til hash.
- kap. 2.3 — hvorfor bucket og radix ikke er lov på
generelle elementer. Den avgrensningen er en fast trekkgrunn her.
- kap. 1.2 — løkketelling, som gir kjøretidene.

Er binærsøk ferskt:
Søking: sekvensielt søk og binærsøk viser det som
kjørende kode i et roligere tempo. Og Lister hvis
array-indeksering trenger en oppfriskning.

Notasjons- og pseudokodeliste

Løkke 1 — binærsøk, og det ene ordet som gir trekk (ca. 14 min)

Du leter etter et navn i en telefonkatalog. Du slår ikke opp på side 1 og
begynner å lese — du slår opp på midten, ser hvilken halvdel navnet må være i, og
gjentar. Hvert oppslag halverer det som er igjen.

Det er binærsøk, og det krever at dataene er sortert. Uten sortering er
det ingen «halvdel navnet må være i», og algoritmen er verdiløs.

Kjøretiden leses rett ut av halveringen, akkurat som i
kap. 1.2: antall ganger du kan halvere $n$ før du står igjen
med ett element, er $\log_2 n$ . Derfor er binærsøk $O(\log n)$ .

Så kommer detaljen som er verdt et poeng i hvert sett den dukker opp: den
varianten av binærsøk som er pensum, returnerer sant eller usant — ikke en
indeks. Skal du ha indeksen, må algoritmen modifiseres, og du må si at du gjør
det.

Binærsøk

O(\log n)

📜Pseudokode-kontrakt: `BinarySearch`

Antagelser om representasjon. A er et sortert array med

n

elementer
indeksert fra 0, og elementene kan sammenlignes. Vi har direkte indeksering,
altså at A[i] er

O(1)

Prebetingelse: A er sortert stigende. Postbetingelse: returverdien er
sant hvis og bare hvis x finnes i A; A er uendret.

Procedure BinarySearch(A, x)
  Input:  sortert array A med n elementer (indeks fra 0), verdi x
  Output: sant hvis x finnes i A, ellers usant
  lav = 0
  hoy = A.length - 1
  while lav <= hoy:
      midt = (lav + hoy) / 2
      if A[midt] er lik x:
          return sant
      if A[midt] < x:
          lav = midt + 1
      else:
          hoy = midt - 1
  return usant

Her er / heltallsdivisjon, så midt er alltid en gyldig indeks.

Invarianten i én setning: hvis x finnes i A, ligger den alltid i
intervallet fra lav til hoy — og intervallet halveres i hver runde.

Kjøretid: hver runde halverer antall gjenværende elementer, så løkka går
$\log_2 n$ runder, og hver runde gjør konstant arbeid. $O(\log n)$ , der $n$ er
antall elementer i A.

Merk hva prosedyren returnerer: sant eller usant. Trenger du indeksen,
må du endre return sant til return midt og return usant til return -1.
Modifikasjonen er triviell — men den må nevnes, og det er nettopp det som er
felle #4 i bokas feilregister: å hevde at pensums binærsøk gir en indeks uten
å si at det må modifiseres.

✏️Eksempel 1: Binærsøk kjørt to ganger

Det sorterte arrayet er A = [2, 5, 9, 12, 17, 23, 31, 40] med $n = 8$ . Kjør
binærsøk etter 23 og etter 20, og tell sammenligningene.

Søk etter 23:

Steg	`lav`	`hoy`	`midt`	`A[midt]`	Sammenligning	Nytt intervall
1	0	7	3	12	mindre enn `x`, gå til høyre	`lav = 4`, `hoy = 7`
2	4	7	5	23	lik `x` — funnet	stopp

Funnet på indeks 5 etter 2 sammenligninger.
Søk etter 20:

Steg	`lav`	`hoy`	`midt`	`A[midt]`	Sammenligning	Nytt intervall
1	0	7	3	12	mindre enn `x`, gå til høyre	`lav = 4`, `hoy = 7`
2	4	7	5	23	større enn `x`, gå til venstre	`lav = 4`, `hoy = 4`
3	4	4	4	17	mindre enn `x`, gå til høyre	`lav = 5`, `hoy = 4`
4	5	4	—	—	`lav > hoy`, intervallet er tomt	ikke funnet

Ikke funnet, etter 3 sammenligninger.

Kontrollregning av kjøretiden. Med $n = 8$ er $\log_2 8 = 3$ , og det verste

søket brukte nøyaktig 3 sammenligninger. Doblet vi arrayet til 16 elementer, ville
det verste søket brukt 4. Det er signaturen til $O(\log n)$ : én ekstra
sammenligning per dobling av $n$ .
Merk steg 3 i det andre søket. Intervallet er nede i ett element, `lav = hoy
= 4. Etter sammenligningen blir lav = 5 og hoy = 4, altså lav > hoy`, og
løkka avsluttes. Det er slik algoritmen konkluderer at verdien ikke finnes — ikke

ved å ha sett på alle elementene, men ved at intervallet der den kunne ligget, er

tomt.
Om returverdien. Begge søkene svarte sant eller usant. Skulle vi hatt
indeksen 5 i det første søket, måtte prosedyren returnert midt i stedet — en
modifikasjon som må nevnes eksplisitt i en besvarelse.

📝Oppgave 1

(Innstegsoppgave, sjanger I — søk i pseudokode, altså at du skriver eller sporer
en søkealgoritme og oppgir kjøretiden.) Det sorterte arrayet er
A = [1, 4, 6, 8, 11, 15, 19].

a) Kjør binærsøk etter 4. Hvilke indekser blir midt?
b) Hvor mange sammenligninger brukte søket?
c) Hva returnerer pensums binærsøk her — indeksen 1, eller noe annet?

Løkke 2 — finn duplikat: tre lovlige svar, tre ulike poengsummer (ca. 13 min)

— naturlig pausepunkt —

Nå til mønsteret som gir flest Del 2-poeng i hele Del 3.

Oppgaven: gitt et usortert array med $n$ elementer, finnes det to som er like?

Det finnes tre korrekte løsninger, og de gir ulikt antall poeng. Dette er
poengtrappen i sin reneste form, og den er verdt å kunne som en form du kan
skrive ned på tretti sekunder.

📜Finn duplikat — de tre trinnene i poengtrappen

Antagelser om representasjon. A er et array med

n

elementer indeksert fra
0. Elementene kan sammenlignes for likhet, og for hash-løsningen også hashes. Vi
kan opprette nye strukturer.

Trinn 3, nederst — dobbel løkke, $O(n^2)$ . Sammenlign hvert par:

for i = 0 to n-1:
    for j = i+1 to n-1:
        if A[i] er lik A[j]:
            return sant
return usant

To nøstede løkker gir $\displaystyle \frac{n(n-1)}{2}$ sammenligninger. Korrekt, og gir
uttelling — men minst.

Trinn 2 — sortér og skann, $O(n \log n)$ . I et sortert array står to like
elementer alltid ved siden av hverandre:

B = MergeSort(A)
for i = 0 to B.length-2:
    if B[i] er lik B[i+1]:
        return sant
return usant

$O(n \log n)$ for sorteringen pluss $O(n)$ for skanningen; sumregelen gir
$O(n \log n)$ . Garantert, uansett input.

Trinn 1, øverst — hash-set, $O(n)$ forventet. Gå gjennom én gang og husk hva
du har sett:

Procedure HarDuplikat(A)
  Input:  array A med n elementer, indeksert fra 0
  Output: sant hvis to elementer i A er like, ellers usant
  S = tomt hash-set
  for i = 0 to A.length-1:
      if Contains(S, A[i]):
          return sant
      Add(S, A[i])
  return usant

Én løkke over $n$ elementer, med $O(1)$ forventet per oppslag. Totalt
$O(n)$ forventet, $O(n^2)$ i verste tilfelle når alt kolliderer.

Er $O(n)$ lavest mulig? Ja. Du må se på hvert element minst én gang for å
kunne konkludere, så ingen algoritme kan komme under $O(n)$ . Skriv den
setningen — den viser at du vet at du har truffet bunnen, og den er en del av
det sensor ser etter.

Én ting du ikke kan gjøre: foreslå bucket eller radix sort som «rask
sortering» når alt du vet er at elementene kan sammenlignes. Det er felle #5 i
bokas feilregister, og et lineært svar som bryter forutsetningen sin, står ikke
øverst i trappen — det står utenfor den. Se
kap. 2.3.

✏️Eksempel 2: Hash-set-løsningen kjørt

Kjør HarDuplikat på A = [14, 3, 9, 22, 3, 7] og vis settet etter hvert steg.

Steg	Element	Allerede i settet?	Settet etter steget
1	14	nei	`{14}`
2	3	nei	`{14, 3}`
3	9	nei	`{14, 3, 9}`
4	22	nei	`{14, 3, 9, 22}`
5	3	ja — duplikat funnet	`{14, 3, 9, 22}`

Returnerer sant etter 5 av 6 elementer.
Legg merke til at løkka stoppet før den var ferdig. Det er ikke en detalj:
algoritmen returnerer så snart svaret er sikkert. I verste tilfelle — ingen
duplikater — går den gjennom alle

n

elementene, og det er den kjøretiden vi
oppgir.
Kjøretid: én løkke over

n

elementer, med ett Contains og ett Add per

runde, hver på $O(1)$ forventet. Totalt $O(n)$ forventet, der $n$ er antall

elementer i A.
Og det ærlige forbeholdet: i verste tilfelle, når alle elementene hasher til
samme plass, koster hvert oppslag $O(n)$ , og totalen blir $O(n^2)$ — nøyaktig like
dårlig som den doble løkka. Det er derfor ordet «forventet» ikke kan utelates.

Sammenlign med sortér-og-skann på samme data. Flettesortering ville gitt
[3, 3, 7, 9, 14, 22], og skanningen ville funnet de to 3-erne som naboer på
indeks 0 og 1. Korrekt svar, $O(n \log n)$ — ett trinn lavere i poengtrappen, men

med en garanti hash-løsningen ikke har.

📝Oppgave 2

Sjanger I

Gitt et usortert array A med $n$ heltall, skriv en algoritme
som avgjør om to elementer er like.

a) Navngi problemet og oppgi antagelser om representasjon.
b) Skriv algoritmen som gir lavest kjøretid.
c) Oppgi kjøretiden, og forklar hvorfor den er lavest mulig.
d) Hva ville du svart hvis oppgaven i tillegg krevde en garantert
kjøretid?

Løkke 3 — finn par som summerer til $x$ (ca. 14 min)

Den tredje faste oppgavetypen, og den har to gode løsninger avhengig av om arrayet
er sortert eller ikke.

Oppgaven: finnes det to elementer i A som summerer til $x$ ?

Er arrayet usortert, er hash-settet svaret igjen — men med en vri: i stedet
for å spørre «har jeg sett dette elementet før?», spør du «har jeg sett
komplementet $x - A[i]$ før?».

Er arrayet sortert, finnes det en løsning uten hash i det hele tatt, og den
er penere: to pekere, én fra hver ende.

To-peker-teknikken

n

📜Finn par — to lovlige veier

Antagelser om representasjon. A er et array med

n

heltall indeksert fra 0.
For hash-varianten må elementene kunne hashes; for to-peker-varianten må A være
sortert.

Vei 1 — usortert array, hash-set, $O(n)$ forventet:

Procedure FinnesPar(A, x)
  Input:  array A med n heltall (indeks fra 0), maalsum x
  Output: sant hvis to elementer i A summerer til x, ellers usant
  S = tomt hash-set
  for i = 0 to A.length-1:
      if Contains(S, x - A[i]):
          return sant
      Add(S, A[i])
  return usant

Rekkefølgen inne i løkka er ikke tilfeldig. Du slår opp først og legger
inn etterpå. Gjør du det motsatt, vil et element som er nøyaktig halvparten av
$x$ finne seg selv og gi et falskt treff — for eksempel $x = 10$ og A[i] = 5
uten at det finnes noen annen 5-er.

Vei 2 — sortert array, to pekere, $O(n)$ garantert:

Procedure FinnesParSortert(A, x)
  Input:  sortert array A med n heltall (indeks fra 0), maalsum x
  Output: sant hvis to elementer i A summerer til x, ellers usant
  i = 0
  j = A.length - 1
  while i < j:
      sum = A[i] + A[j]
      if sum er lik x:
          return sant
      if sum < x:
          i = i + 1
      else:
          j = j - 1
  return usant

Invarianten i én setning: ethvert par som summerer til $x$ ligger alltid innenfor
i til j — for når A[i] + A[j] < x, kan A[i] ikke pares med noe innenfor
intervallet i det hele tatt, siden A[j] er den største muligheten.

Kjøretid: hvert steg flytter én peker, og de kan flytte høyst $n$ ganger til
sammen. $O(n)$ , garantert — ikke bare forventet.

Poengtrappen for denne oppgaven:

Situasjon	Beste løsning	Kjøretid
Sortert array	to pekere	$O(n)$ garantert
Usortert array	hash-set	$O(n)$ forventet
Usortert, garanti kreves	sortér og bruk to pekere	$O(n \log n)$
Naiv	dobbel løkke over alle par	$O(n^2)$

Merk den tredje raden: sorterer du selv for å kunne bruke to pekere, koster
sorteringen

O(n \log n)

, og den dominerer. Du får garantien, men mister
lineariteten.

✏️Eksempel 3: To pekere kjørt på et sortert array

Det sorterte arrayet er A = [2, 5, 9, 12, 17, 23, 31, 40]. Finnes det to
elementer som summerer til $x = 40$ ?

Steg	`i`	`j`	`A[i]`	`A[j]`	Sum	Handling
1	0	7	2	40	42	større enn `x`, flytt `j` tilbake
2	0	6	2	31	33	mindre enn `x`, flytt `i` fram
3	1	6	5	31	36	mindre enn `x`, flytt `i` fram
4	2	6	9	31	40	lik `x` — paret (9, 31) funnet

Returnerer sant etter 4 steg.
Se på steg 1. Summen

2 + 40 = 42

er for stor. Vi flytter j tilbake — og
det som skjer da, er at vi utelukker alle par som inneholder 40. Hvorfor? Fordi
2 er det minste elementet i intervallet, så

2 + 40

er den minste summen 40
kan inngå i. Er den allerede for stor, kan 40 ikke være med i noe par.

Det er hele argumentet bak metoden, og det er verdt å skrive i en besvarelse:

hver flytting utelukker en hel rad eller kolonne av mulige par, og derfor holder
det med $n$ steg i stedet for $n^2$ .
Kontrollkjøring der svaret er nei. På A = [1, 3, 4, 7, 10, 14] med
$x = 20$ :

Steg	`i`	`j`	`A[i]`	`A[j]`	Sum	Handling
1	0	5	1	14	15	mindre enn `x`, flytt `i` fram
2	1	5	3	14	17	mindre enn `x`, flytt `i` fram
3	2	5	4	14	18	mindre enn `x`, flytt `i` fram
4	3	5	7	14	21	større enn `x`, flytt `j` tilbake
5	3	4	7	10	17	mindre enn `x`, flytt `i` fram
6	4	4	—	—	—	`i` og `j` møtes — ingen par finnes

Returnerer usant etter 5 steg. Med

n = 6

er det under

n

steg, som
stemmer med at hvert steg flytter én peker og pekerne til sammen kan flytte høyst

$n$ ganger.
Poengtrapp-notat. På et sortert array er to pekere det øverste trinnet, og

det er strengt bedre enn hash-løsningen, fordi $O(n)$ her er garantert og ikke
bare forventet. Det er verdt å si eksplisitt: «siden arrayet allerede er sortert,
gir to pekere $O(n)$ garantert, uten hashingens verstetilfelle».

📝Oppgave 3

Sjanger I

Gitt et usortert array A med $n$ heltall og et tall x, skriv
en algoritme som avgjør om to elementer summerer til x.

a) Navngi problemet, oppgi antagelser og skriv algoritmen.
b) Oppgi kjøretiden og begrunn hvorfor den er lavest mulig.
c) Hvorfor må oppslaget komme før innsettingen i løkka?

Typiske feil

- Å hevde at binærsøk returnerer en indeks. Pensums variant returnerer sant
eller usant. Skal du ha indeksen, må prosedyren modifiseres — og du må si
det. Dette er felle #4 i bokas feilregister, og den gir eksplisitt trekk.
- Å bruke binærsøk på et usortert array. Uten sortering finnes det ingen
halvdel å kaste. Nevn alltid at forutsetningen er oppfylt.
- Å foreslå bucket eller radix sort i «sortér og skann». De krever et kjent,
begrenset verdiområde. Felle #5 — se kap. 2.3.
- Å skrive $O(n)$ uten «forventet» på en hash-løsning. Verste tilfelle er
$O(n^2)$ . Kjøretiden må matche algoritmen du faktisk ga.
- Å legge inn i hash-settet før oppslaget i parsøket. Da kan et element pares
med seg selv. Slå opp først, legg inn etterpå.
- Å bruke en dobbel løkke der en lineær løsning finnes. $O(n^2)$ er korrekt og
gir uttelling, men det er nederste trinn i poengtrappen. Å velge verktøy er å
velge poeng.
- Å bruke $n$ uten å definere det. Felle #10 — å oppgi kjøretid uten å si
hva problemstørrelsen er. Én setning holder: « $n$ er antall elementer i A».

📝Oppgave 4

Sjanger I

Du får et sortert array A med $n$ heltall og et tall x.

a) Skriv en algoritme som finner et par som summerer til x, uten å bruke
hashing.
b) Oppgi kjøretiden, og si hvorfor den er strengt bedre enn
hash-løsningen her.
c) Hva ville du gjort hvis arrayet var usortert og du måtte ha en garantert
kjøretid?

📝Oppgave 5

Sjanger I, krevende

En besvarelse lyder:

«Jeg bruker binærsøk til å finne indeksen til hvert komplement x - A[i]. Det
gir $O(\log n)$ per element og $O(n \log n)$ totalt, som er lavest mulig for et
usortert array.»

a) Finn feilene.
b) Under hvilken forutsetning ville strategien vært riktig?
c) Skriv en korrekt besvarelse for det usorterte tilfellet.

📝Oppgave 6

Sjanger I, krevende

Du får et sortert array A med $n$ heltall og en
verdi x, og skal returnere indeksen til x, eller $-1$ hvis den ikke
finnes.

a) Skriv algoritmen, og si eksplisitt hva du endrer fra pensums binærsøk.
b) Oppgi kjøretiden.
c) Hvorfor virker ikke denne algoritmen på en lenket liste?
d) Hva ville du gjort hvis A var usortert og du skulle finne indeksen?

Begrepsbank

Begrepsbanken er flashcard-/repetisjonsstoff — den gjentar det du nettopp har
lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet gjelder
kjernestoffet.

Binærsøkets forutsetninger

O(1)

Returverdien fra pensums binærsøk

sant eller usant, ikke en indeks. Vil du ha indeksen, endrer du return sant til return midt og return usant til return -1 . Modifikasjonen er triviell, men den må nevnes — å hevde at binærsøk gir en indeks uten forbeholdet er felle #4 og gir eksplisitt trekk.

Binærsøkets kjøretid

O(\log n)

Terminering ved tomt intervall

O(\log n)

Duplikatsøk med hash-set

O(n)

Duplikatsøk ved sortering

O(n \log n)

Komplement-oppslaget i parsøket

x - A[i]

Oppslag før innsetting

x = 10

To-peker-invarianten

x

To pekere kontra hash-set

O(n)

Poengtrappen for søkeoppgaver

O(n)

«Er dette lavest mulig?»

O(n)

Firestegsformen på et Del 2-svar

n

Når lineært søk er det riktige svaret

O(n)

Repetisjon — kapitlet på ett kort

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 Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.

3.4 Søk i pseudokode — binærsøk, finn duplikat og finn par

Forkunnskaper

Løkke 1 — binærsøk, og det ene ordet som gir trekk (ca. 14 min)

Løkke 2 — finn duplikat: tre lovlige svar, tre ulike poengsummer (ca. 13 min)

Løkke 3 — finn par som summerer til xxx (ca. 14 min)

Begrepsbank

Løkke 3 — finn par som summerer til $x$ (ca. 14 min)