Hint til oppgave 5
Boken har generelle tips til programmering av binærsøk. I denne oppgaven var det imidlertid en tilleggsutfordring: Ved søk etter element som ikke finnes, skal metoden finnPos returnere et negativt tall.
Dette er nyttig i forbindelse med innsetting og sletting. Vi kan bruke binærsøk for effektivt å avgjøre om operasjonen lar seg gjennomføre. Men hvordan skal vi "kode" at en gitt verdi ikke finnes?
Se på følgende heltallstabell:
| 2 | 7 | 14 | 42 | 76 | 84 | 0 | 0 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
La oss si at vi i tillegg til selve tabellen har en variabel nesteLedige som her vil ha verdien 6. Den logiske tabellen går altså fra og med posisjon 0 til og med posisjon 5.
Ved søk etter verdier som finnes, skal posisjonen til tallet returneres. F.eks. skal finnPos(14) returnere 2 og finnPos(84) returnere 5. Merk spesielt at finnPos(2) skal returnere 0.
Ved søk etter tall som ikke finnes i tabellen, er planen å returnere et negativt tall som peker ut hvor tallet kan settes inn - slik at tabellen fortsatt er sortert (alle større tall må selvsagt flyttes én posisjon lenger ut).
En grei løsning er da å la -1 peke ut den første posisjonen (altså 0), la -2 peke ut den andre posisjonen (altså 1) osv. Husk at returverdi 0 fra finnPos betyr at søket var vellykket!
Eksempel: Vi skal sette inn tallet 8 i tabellen over, og kaller finnPos(8) for å finne riktig posisjon.
- I metoden finnPos starter vi et binærsøk som konkluderer med at 8 ikke finnes. Samtidig vil vi finne ut at 8 bør inn på posisjon 2.
- Metoden finnPos returnerer dermed tallet -3.
- Fordi finnPos gir oss -3 som svar (negativt tall) vet vi at 8 ikke finnes i tabellen, og vi kan finne posisjonen ved -(-3)-1 = 2.
Du skal programmere en søkemetode mot en referansetabell av type Ansatt[]. Prinsippet blir det samme, tenk at tallene i eksempelet over er ansattnumre.
