Oppgave 1

Første versjon av binærsøk står til venstre. Gjennomsnittet er 62/12. Andre versjon står til høyre. Gjennomsnitt: 59/12.

Oppgave 2

Gjennomsnittet for 1. versjon av binærsøk blir (1 + 2*3 + 4*5 + 8*7)/15 = 83/15.

Gjennomsnittet for 2. versjon av binærsøk blir (2 + 4 + 3 + 6 + 5 + 5 + 4 + 8 + 7 + 7 + 6 + 7 + 6 + 6 + 5)/15 = 81/15.

Oppgave 3

Gjennomsnittet for 1. versjon av binærsøk blir (1 + 2*3 + 4*5 + 8*7 + 3*9)/15 = 110/15.

Gjennomsnittet for 2. versjon av binærsøk blir (2 + 4 + 3 + 6 + 5 + 5 + 4 + 8 + 7 + 7 + 6 + 7 + 6 + 6 + 5 + 7 + 7 + 6)/15 = 101/15.

Oppgave 5

Flg. metode teller opp og returnerer antall sammenligninger som utføres når versjon 2 av binærsøk brukes, enten den søkte verdien ligger i tabellen eller ikke.

  public static int antallBinærsøk(int[] a, int verdi)
  {
    int v = 0, h = a.length - 1;
    int antall = 0; // antall sammenligninger

    while (v <= h)
    {
      int m = (v + h)/2;
      int midtverdi = a[m];

      antall++;
      if (verdi > midtverdi) v = m + 1;
      else
      {
        antall++;
        if (verdi < midtverdi) h = m - 1;
        else return antall;
      }
    }
    return antall;   // returnerer antallet sammenligninger
  }

Flg. programbit lager en tabell som inneholder tallene fra 1 til n, søker fortløpende etter hvert av disse tallene og finner det sammenlagte antallet sammenligninger som utføres. Gjennomsnittet får vi ved å dele med n. Deretter regnes tilnærmingsverdien 1,5*log₂(n+1) - 1 ut. Ved å variere n kan en se hvor nær tilnærmingsverdien er den eksakte verdien for forskjellige verdier av n.

   int n = 100;

   int[] a = new int[n];
   for (int i = 0; i < n; i++) a[i] = i + 1;

   int antall = 0;
   for (int i = 1; i <= n; i++)
     antall += antallBinærsøk(a,i);

   double e = ((double)antall)/n;
   System.out.println("Eksakt gjennomsnitt: " + e);

   double g = 1.5*Math.log(n+1)/Math.log(2)- 1;
   System.out.println("Tilnærmet gjennomsnitt: " + g);