Binær kontra sekventiel søgning

2: Du starter fra starten, og pløjer hele det element der skal søges i igennem fra ende til anden.

3: Kan ikke huske hvad binær søgning er, men en rekursiv funktion, er en funktion der kalder sig selv.

Eksempel i Java:

public class Search {
    public static void main(String[] args) {
        int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        System.out.println(seqsearch(a,7) + " " + seqsearch(a,13));       
        System.out.println(binsearch(a,7) + " " + binsearch(a,13));       
        System.out.println(reqbinsearch(a,7) + " " + reqbinsearch(a,13));       
    }
    public static boolean seqsearch(int[] a, int v) {
        for(int i = 0; i < a.length; i++) {
            if(a[i] == v) {
                return true;
            }
        }
        return false;
    }
    public static boolean binsearch(int[] a, int v) {
        int l = 0;
        int r = a.length - 1;
        int ix;
        while(l <= r) {
            ix = (r + l) / 2;
            if(a[ix] == v) {
                return true;         
            } else if(a[ix] < v) {
                l = ix + 1;
            } else {
                r = ix - 1;
            }
        }
        return false;
    }
    private static boolean reqbinhelp(int[] a, int v, int l, int r) {
        if (l > r) {
            return false;
        }
        int ix = (r + l) / 2;
        if(a[ix] == v) {
            return true;         
        } else if(a[ix] < v) {
            return reqbinhelp(a, v, ix + 1, r);
        } else {
            return reqbinhelp(a, v, l, ix - 1);
        }
    }
    public static boolean reqbinsearch(int[] a, int v) {
        return reqbinhelp(a, v, 0, a.length - 1);
    }
}

Sekventiel og binær søgning er "rigtige".

Rekursiv binær søgning har jeg aldrig set elle rprøvet før, så der
har jeg gætte mig lidt frem.

1. du bruger halveringsprincippet til at søge med (kræver det er sorteret)
2. du starter i den ene ende og bliver ved til du har fundet det
3. samme som 1 men kalder sig selv til halveringer osv.

1 har tidskomplextiteten O(log2(n))
2 har tidskomplextiteten O(n)
3 har samme som 1

Altså binær søgning er hurtigere og jo flere data des større er forskellen.

Og du ved at:
  sekventiel søgning  er O(n)
  binær søgning er O(log(n))

Og den ikke-rekursive variant af binær søgning vil nok være
lidt hurtigere end den rekursive.

Men binær søgning kræver at data er sorteret.

Sekventiel søgning virker på usorterede data også.

arne din tidskomplexitet er forkert for binær søgning.

Det er totalslogaritmen man skal bruge ikke den alm. logaritme.

disky du vrøvler !

O(x) angiver hvad tiden er propertional med - ikke noget
om hvilken konstant der skal ganges på.

Nu gælder det at forholdet mellem log2(x), loge(x) og log10(x) er
konstant.

Elementær egenskab ved algoritmer.

Man kan derfor bruge log2 eller loge eller log10 eller log237 efter
behag.

Nej jeg vrøvler ikke, jeg ved udemærket at det forskels mæssigt ikke gør en forskel når man sammenligner tallene for 2 forskellige mængder, det er jo ligesom en af reglerne for logaritmen, hvis du nu ikke lige vidste det.

Men den korrekte måde at beskrive det på er log2(n) det det netop er BINÆRT havde det været trinært (3 tals system) havde det været log3(n).

Hvilket tydeligt er beskrevet i bøger om algoritme teori.

Husk 'smid ikke med sten hvis du bor i glashus' !

Prøv for sjov skyld at søge på Google efter:

"binary search" "O(log n)" ->  8700 hits
"binary search" "O(log2 n)" ->  341 hits
"binary search" "O(logn)" -> 1050 hits
"binary search" "O(log2n)" -> 265 hits

og drag dine konklusioner om hvad folk bruger.

Det er normalt at bare at angive log i big-O analyse.

Af indlysende årsager. O(log2(n)) og O(log3(n)) er nemlig
præcis det samme - derfor giver det mest mening at kalde det
O(log(n)).

Man får først brug for log2 når man går fra big-O til at
specifikt at skulle tælle operationer - der er forskel på
log2(n) og 2*log3(n).

Og så hedder det iøvigt ternær ikke trinær.

For en god dansk referance til binær søgning og ternær søgning
(som naturligvis bruger O(log(n)) til angivelse af big-O og log2(n) til
angivelse af antal sammenligninger !) se:
  http://www.dat.ruc.dk/~keld/teaching/algoritmik_e99/Slides/06_Soegning_I.ppt

Tak for alle svarene..Jeg kigger stadig på dem.. :)

Mvh Casualty

Ja O(log(n)) er brugbar ligesom O(log2(n)) men ved et binært søgetræ giver det mere mening samtidigt at angive man har forstået at det er totalslogaritmen man skal bruge ved beregninger osv.
Sådanne detalje er det som skal til for f.eks. at få 13 til eksamen istedet for 'kun' 11. Da det viser man har forståelse for de dybere ting.

Eller så får man 7 fordi man ikke har forstået hvad big-O drejer sig om.

Det gælder måske i dit tilfælde, men jeg fik noget mere end 7 til min eksamen i algoritme teori.

Forhåbentligt ikke ved at snakke om O(log2(n)) eller O(2*n) eller lignende.

Jeg ved da ikke hvordan du fik dit 7 tal, det må du da ærligt talt bedst vide selv.

Men til min eksamen var der også om tidskomplexitet, hvilket gik rigtigt fint.

p.s. Nu gider jeg ikke at spilde mere tid på denne tråd, du fortsætter jo alligevel bare i bedste duracell stil, som så mange gange før.

Det er vist nødvendigt at pinde det lidt mere ud. Jeg forsøgte at forklare
at hvis man brugte udtryk som O(log2(n)) til eksamen var det mere
sandsyneligt at blive hevet ned fra 11 til 7 for ikke at have forstået
big-O som blive hevet op fra 11 til 13. Og jeg ved ikke hvordan du har
kunnet læse det som, at jeg skulle havet fået 7 til en algoritme eksamen.

Ja og jeg sagde at man måske kunne få 13 istedet for 11 for at præciserer hvorfor O(log2(n)) er mere rammende end O(log(n)) ved et binært træ.

Ved at det ved sammenligning af tidskomplexiterer ved f.eks. sequentiel søgning i forhold til et binært træ søgning, siger mere om forståelse, i form af at man har fortståelsen for at log2(n) angiver antallet af sammenligninger der skal anvendes.

Det er som nævnt tidligere en lille detalje, som du åbenbart synes er ligegyldigm men jeg ved at nogle censorer belønner sådanne detaljer.

Så for at skære det helt ud i pap:
Ved sammenligning af tidskomplexiteten betyder det ikke noget, men det viser dybere forståelse for selve algoritmerne. Om man så bekymrer sig om dette er en helt anden sag, men det skader jo ikke at angive denne extra information :)

Nå tak for idag, nu er det lukketid.