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/168 (upplaga 1/2) och i en trimmad version på sidan 130/170. Notera att den första upplagan använder metoden compares(), istället för den bättre, redan inbyggda compareTo(). Använd compareTo().

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 1000000 = 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 klassens metoder (t ex inuti main()). Dom kallas därför klassvariabler eller 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 inuti ett block (som t ex satserna inuti en slinga) - då dör den vid utträdet ur blocket. Utrycken som hör till for eller while anses tillhöra satsens block.

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[] dagskassor;

    public static void main(String[] args) {
	läsIn();
	skrivUt();
	int totalkassa = totalkassa();
	int maxkassa = maxkassa();
	System.out.println("Total: " + totalkassa + ", max: " + maxkassa);
    }

    static void läsIn() {
	System.out.print("Antal dagar: ");
	int n = Mio.getInt();
	dagskassor = new int[n];

	for (int i = 0; i < dagskassor.length; ++i) {
	    System.out.print("dagskassa " + (i+1) + ": ");
	    dagskassor[i] = Mio.getInt();
	}
    }

    static void skrivUt() {
	for (int i = 0; i < dagskassor.length; ++i) 
	    System.out.println((i+1) + " : " + dagskassor[i]);
    }

    static int totalkassa() {
	int tot = 0;
	for (int i = 0; i < dagskassor.length; ++i)
	    tot = tot + dagskassor[i];
	return tot;
    }

    static int maxkassa() {
	int max = dagskassor[0];
	for (int i = 1; i < dagskassor.length; ++i)
	    if (dagskassor[i] >max)
		max = dagskassor[i];
	return max;
    }
}


^ Upp till kurssidan.


Sidansvarig: <efo@nada.kth.se>
Senast ändrad 18 oktober 2002
Tekniskt stöd: <webmaster@nada.kth.se>