Nada

Föreläsning 5: Binärsökning.

Binärsökning i vektor

Jag tänker på ett ord i ordlistan. Kan du gissa vilket?
LAT
Nej, det kommer före LAT.
FUL
Nej, det kommer efter FUL.
- - - (femton gissningar senare) - - -
JUXTAPOSITION
Rätt! Det tog sjutton gissningar.
Det finns knappt tvåhundratusen ord i SAOL (Svenska Akademiens Ordlista). Den första gissningen LAT kommer i mitten och därmed skärs antalet möjliga ord ner till hälften. Eftersom antalet ord i SAOL är ungefär 2 höjt till 17 är man nere i ett enda möjligt ord efter sjutton halveringar.

Metoden kallas binärsökning och den finns programmerad av Weiss på sidan 129 (och i en trimmad version på sidan 130).

Komplexitet för binärsökning

Om vektorns längd är N kommer binärsökningen att kräva ungefär logN jämförelser. Här betyder log tvålogaritm, dvs log 2 = 1, log 4 = 2, log 8 = 3,..., log 1000 = ca 10, log 1 000 000 = ca 20 etc.

Tvålogaritmen är inte ett heltal, men bör avrundas nedåt om man frågar efter genomsnittskomplexitet och avrundas uppåt om man frågar efter värsta fallets komplexitet.

Globala och lokala variabler

Variabler som deklareras högst upp i klassen kan användas överallt i klassen, inne i main och i alla metoder. Dom kallas därför globala variabler. Variabler som deklareras inne i main eller någon annan metod är oåtkomliga utifrån. Sådana lokala variabler föds när exekveringen går in i metoden och dör när exekveringen lämnar metoden. Ännu lokalare blir variabeln om den deklarerats inne i en slinga ­ då dör den vid utträdet ur slingan.

Variabler som används i alla metoder är det praktiskt att ha globala. I det här exemplet handlar allt om en vektor med dagskassor för många dagar, och den vektorn har fått vara global. Observera att antalet dagar inte är känt vid körningens början, och att minnesutrymmet för vektorn därför skapas först av anropet LäsIn().

class Kassor                                                        {
  static int[] dagskassa                                            ;
  static int N                                                      ;
  static void SkrivUt()                                             {
    for(int i=0;i<N;i++) System.out.println((i+1)+"  "+dagskassa[i]);}
  static int Totalkassa()                                           {
    int tot=0                                                       ;
    for(int i=0;i<N;i++) tot=tot+dagskassa[i]                       ;
    return tot                                                      ;}
  static int Maxkassa()                                             {
    int max=dagskassa[0]                                            ;
    for(int i=1;i<N;i++) if(dagskassa[i]>max) max=dagskassa[i]      ;
    return max                                                      ;}
  static void LäsIn()                                               {
    System.out.print("Antal dagar: ")                               ;
    N=Mio.GetInt()                                                  ;
    dagskassa = new int[N]                                          ;
    for(int i=0;i<N;i++)                                            {
      System.out.print("dagskassa "+(i+1)+": ")                     ;
      dagskassa[i]=Mio.GetInt()                                     ;}}
  public static void main(String[] args)                            {
    LäsIn()                                                         ;
    SkrivUt()                                                       ;
    int totalkassa=Totalkassa()                                     ;
    int maxkassa=Maxkassa()                                         ;
    System.out.println("Total:"+totalkassa+", max: "+maxkassa)      ;}}

Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 3 februari 1999
Tekniskt stöd: <webmaster@nada.kth.se>