BinaerSok.java [Last ned]

import static java.lang.System.*;
 
 
/*
 *  Program som deklarerer og tester en metode for
 *  å gjøre binærsøk i en sortert ansattsamling.
 *
 *  Testing gjøres ved hjelp av en egen testmetode
 *  som kaller søkemetoden med en søkeverdi og
 *  sammenligner returverdien med en fasit.
 *  
 *  Se junit.org for et profesjonelt testeverktøy.
 *
 */
public class BinaerSok {
 
  private static Ansatt[] tabell;
  private static int      nesteLedige;
 
  public static void main(String[] args) {
 
    // Setter av plass til 10 objekt
    tabell = new Ansatt[10];
    nesteLedige = 0;
 
    // Tester finnPos-metoden på tom tabell
    boolean ok = testFinnPos(99,  -1);  // Ansatt 99 skal inn i pos 0
 
    // Fyller tabellen med 3 Ansatt-objekt
    // satt inn i stigende rekkefølge.
    tabell[0] = new Ansatt(5,  "Jan",  "Li",    420000);
    tabell[1] = new Ansatt(10, "Lise", "Moen",  521000);
    tabell[2] = new Ansatt(15, "Kari", "Enger", 477000);
 
    nesteLedige = 3;
 
    // Tester finnPos-metoden
 
    // Søk etter objekt som finnes
    ok = ok && testFinnPos(5,  0);  // Ansatt 5 ligger i pos 0
    ok = ok && testFinnPos(10, 1);
    ok = ok && testFinnPos(15, 2);
 
    // Søk etter objekt som ikke finnes
    ok = ok && testFinnPos(1,  -1);   // Ansatt 1 skal inn i pos 0
    ok = ok && testFinnPos(7,  -2);   // Ansatt 7 skal inn i pos 1
    ok = ok && testFinnPos(12, -3);   // Ansatt 7 skal inn i pos 2
    ok = ok && testFinnPos(20, -4);
 
    // Setter inn en ansatt til slik at tabellen
    // inneholder et partall antall ansatte.
    tabell[3] = new Ansatt(17, "Mette", "Lier", 770000);
    nesteLedige = 4;
 
    // Gjentar tester av finnPos-metoden
 
    // Søk etter objekt som finnes
    ok = ok && testFinnPos(5,  0);
    ok = ok && testFinnPos(10, 1);
    ok = ok && testFinnPos(15, 2);
    ok = ok && testFinnPos(17, 3);
 
    // Søk etter objekt som ikke finnes
    ok = ok && testFinnPos(1,  -1);
    ok = ok && testFinnPos(7,  -2);
    ok = ok && testFinnPos(12, -3);
    ok = ok && testFinnPos(16, -4);
    ok = ok && testFinnPos(20, -5);
 
    if (ok)
      out.println("Alle tester ok.");
  }
 
 
  // Finner posisjonen til et Ansatt-objekt, gitt et
  // ansattnr. Hvis objektet ikke finnes, returnerer
  // metoden en negativ verdi pos, som er slik at et
  // evt. nytt objekt med dette ansattnummeret skal
  // inn på posisjon -pos-1.
  //
  // Antar at tabellen er sortert mhp ansattnummer,
  // og kan dermed bruke binærsøk.
  private static int finnPos(int ansNr) {
 
    boolean funnet = false;
    int nedre = 0;
    int øvre = nesteLedige-1;
    int pos = 0;
 
    while (!funnet && nedre<=øvre) {
      pos = (nedre+øvre) / 2;
 
      if ( tabell[pos].getAnsNr() == ansNr )
        funnet = true;
      else if (tabell[pos].getAnsNr() < ansNr)
        nedre = pos+1;
      else
        øvre = pos-1;
    }
 
    if ( funnet )
      return pos;
    else {
      if (nesteLedige == 0) // tom tabell
        return -1;
      else {
        if (tabell[pos].getAnsNr() < ansNr)
          pos++;
        // Nytt objekt skal inn i posisjon pos.
        // Dette blir kodet som posisjon -(pos+1).
        return -(pos+1);
      }
    }
  }
 
  // Metode for å teste finnPos-metoden.
  // Tar et ansattnr og en posisjon (fasit) som parametre,
  // og returnerer true hvis finnPos(ansNr) returnerer fasit.
  private static boolean testFinnPos(int ansNr, int fasit) {
    int pos = finnPos(ansNr);
    boolean ok = ( pos == fasit );
    if (!ok)
      out.println("Søk etter " + ansNr + " feilet. Returnerte " + pos);
    return ok;
  }
 
}
Kildekode blir vist ved hjelp av GeSHi.