Oppgave 1

  int[] a = {3,8,10,12,14,16,21,24,27,30,32,33,34,37,40};

  System.out.println(Tabell.binærsøk(a,32));  // utskrift: 10
  System.out.println(Tabell.binærsøk(a,31));  // utskrift: -11
  System.out.println(Tabell.binærsøk(a,3));   // utskrift: 0
  System.out.println(Tabell.binærsøk(a,2));   // utskrift: -1
  System.out.println(Tabell.binærsøk(a,40));  // utskrift: 14
  System.out.println(Tabell.binærsøk(a,41));  // utskrift: -16

Oppgave 2

Vi får -11 som returverdi. Det svarer til -(-11 + 1) = 10 som innsettningspunkt. Men innsettingspunktet for 26 relativt til hele tabellen er 15.

Oppgave 3

1	3	4	4	5	7	7	8	9	10	10	12	15	15	15
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Et sortert tabell med 15 verdier og mange av dem like

Her er poenget at en må bruke 1. eller 2. versjon av binærsøk.

1. Med verdi = 4 får vi 3 som indeks. Det svarer til den siste av de to 4-erne.
2. Med verdi = 7 får vi 5 som indeks. Det svarer til den første av de to 7-erne.
3. Med verdi = 10 får vi 9 som indeks. Det svarer til den første av de to 10-erne.
4. Med verdi = 15 får vi 13 som indeks. Det svarer til den midterste av de tre 15-tallene.

Oppgave 5

Antall elementer i et ikke tomt intervall a[v:h] er lik h - v + 1. Hvis intervallet a[v:h] har et odde antall verdier, må v + h være et partall og (v + h)/2 indeks til midten. Men (v + h + 1)/2 = (v + h)/2 + 1/2 = (v + h)/2 når operasjonen / er heltallsdivisjon.

Hvis antallet i a[v:h] er et partall, må v + h være et oddetall og dermed v + h + 1 et partall. La k = (v + h + 1)/2. Da vil a[v:k-1] og a[k:h] være like lange siden k - 1 - v + 1 = (h - v + 1)/2 og h - k + 1 = (h - v + 1)/2. Det betyr at (v + h + 1)/2 er rett til høyre for den egentlige midten.

Oppgave 6

  public static int binærsøk(int[] a, int fra, int til, int verdi)
  {
    Tabell.fratilKontroll(a.length,fra,til);

    int v = fra, h = til - 1;

    while (v < h)  // obs. må ha v < h her og ikke v <= h
    {
      int m = (v + h + 1)/2;  // heltallsdivisjon - finner midten

      if (verdi < a[m]) h = m - 1;  // verdi må ligge i a[m+1:h]
      else v = m;                   // verdi må ligge i a[v:m]
    }
    if (h < v || verdi < a[v])return -(v + 1);  // ikke funnet
    else if (verdi == a[v]) return v;           // funnet
    else return -(v + 2);                       // ikke funnet
  }

Oppgave 7

Til intervallsøk i en heltallstabell bruker vi 3. versjon av binærsøk. Et søk etter fraverdi, vil gi posisjonen til den første forekomsten hvis det er flere forekomster, eller eventuelt innsettingspunktet hvis den ikke finnes. De øvrige aktuelle verdiene finner vi fra og med denne og videre. Hvis det er få av dem som er mindre enn tilverdi kan det være mest lønnsomt å hente ut én og én. En slik løsning er laget lenger ned. Hvis det er mange, vil det være mest effektivt å la binærsøk gi oss posisjonen (eller eventuelt innsettingspunktet) til tilverdi. Her kommer en slik versjon:

  public static int[] binærIntervallsøk(int[] a, int fraverdi, int tilverdi)
  {
    int fra = binærsøk(a,0,a.length,fraverdi);  // 3. versjon av binærsøk

    if (fra < 0) fra = -(fra + 1);  // posisjon eller innsettingspunkt

    // Søker i a[fra:a.length>
    int til = binærsøk(a,fra,a.length,tilverdi);  // 3. versjon av binærsøk

    if (til < 0) til = -(til + 1);  // posisjon eller innsettingspunkt

    // Intervallet a[fra:til> inneholder de aktuelle verdiene
    return Arrays.copyOfRange(a, fra, til);
  }

Alternativ løsning:

  public static int[] binærIntervallsøk(int[] a, int fraverdi, int tilverdi)
  {
    // Her må vi bruke 3. versjon av binærsøk
    int fra = Tabell.binærsøk(a,0,a.length,fraverdi);

    if (fra < 0) fra = -(fra + 1);

    // Nå er fra enten posisjonen til første forekomst av fraverdi
    // eller lik innsettingspunktet til fraverdi.

    int til = fra;
    for ( ; til < a.length && a[til] < tilverdi; til++);

    // Nå er til posisjonen til første verdi som ikke skal være med,
    // dvs. intervallet a[fra:til> inneholder de aktuelle verdiene

    int[] b = new int[til - fra];  // hjelpetabell
    System.arraycopy(a,fra,b,0,b.length); // a[fra:til> over i b

    return b;  // returnerer de aktuelle verdiene
  }