Avatar billede backupmand Nybegynder
09. april 2001 - 00:21 Der er 12 kommentarer og
1 løsning

Tvivl omkring binær søgning

Mit problem ligger i, at jeg ikke kan se at det
er det rigtige tal, der returneres.

Min metode (kopieret fra en bog)
er en targetted binary search funktion
på et sorteret array, f.eks. 1,3,5,7,9.
(arraysize=5)

Koden her returnerer, som jeg ser det middle-værdien,
når Element[middle]==target, altså når det tal der
skal findes er lig med Element\'s indeksposition ved
middle. Jeg kan ikke se, at den skulle returnere target.
(det rigtige tal)

Jeg forstår det ikke som boget forklarer det.

________________________________
Koden:

int TargetSearch (int target) // returnerer en værdi hvis den er fundet
{
    int top=ArraySize-1; // 4 går jeg ud fra (arraysize erklæres ved konstruktørkald)
        int bottom=0;
    int middle;

    while (top>=bottom)
    {
    middle=(top+bottom)/2;
    if (Element[middle]==target) // Element array erklæret på klasseniveau
        return middle; // det er dette jeg ikke forstår   
    else if (Element[middle]<target)
            bottom=middle+1;
      else
        top=middle+1;   
    }       
    throw new SearchException(\"Target ikke fundet\");       
   
}


Avatar billede erikjacobsen Ekspert
09. april 2001 - 00:24 #1
Det gør det nu, fordi hvis du ikke rammer target, så gør du intervallet mindre
indtil det enten er tomt eller du rammer target. Det der returneres er
positionen på det element du leder efter.
Avatar billede netsrac Praktikant
09. april 2001 - 00:26 #2
Som jeg ser det, finder den positionen i arrayet Element og returnerer den hvis det er lig med det tal som kommer ind som target.

Når den måder den rigtige bryder den ud af funktionen ellers forsætter den til bottom bliver ligeså stor som top.
Avatar billede stigc Nybegynder
09. april 2001 - 00:26 #3
Det har ikke noget med middel værdi\'er at gøre. Søgning udnytter at arrayet er sorteret, og starter derfor med at undersøge det midterste element. Hvis den ikke findes her kan den efterfølgende udelukke halvdelen af elementerne. osv. osv. Det giver en meget hurtiger søgning end ved lineær søgning.
Avatar billede disky Nybegynder
09. april 2001 - 09:18 #4
Hejsa den routine ser ud til at være en korrekt binær søgeroutine, og den ser også ud til at virke om den skal.

Så du har ikke noget at være bange for :)
Avatar billede backupmand Nybegynder
09. april 2001 - 10:50 #5
Er der nogen der kan forklare mig om binær søgning
er en log n søgefunktion...
Avatar billede disky Nybegynder
09. april 2001 - 10:51 #6
det er den

hvor log er 2\'tals logaritmen !
Avatar billede backupmand Nybegynder
09. april 2001 - 15:40 #7
ok, og så spørger jeg dumt (for jeg vil gerne
acceptere svaret når jeg har forstået det)

Vil det så sige at den gennemsnitlige søgetid
ved binær søgning er n2 (n opløftet i 2)?
pga binær = 2? En almindelig sekventiel søgnings
gennemsnitlige søgetid er n/2 hvor søgetiden er proportional med arrayets/vektorens/listens længde, så vidt jeg forstår.
Avatar billede disky Nybegynder
09. april 2001 - 15:42 #8
normalt søgetid ved linær søgning er O(n) dobbelt så mange elementer dobbelt så lang tid.

ved binær søgning er O(log(n))
Avatar billede disky Nybegynder
09. april 2001 - 15:43 #9
hmmm nu bliver jeg selv i tvivl, men den er hurtigere :)
Avatar billede disky Nybegynder
09. april 2001 - 15:47 #10
ups tiden er

O (log(n)/log(2)) for at sikre det er 2 tals logartimen vi bruger
Avatar billede erikjacobsen Ekspert
09. april 2001 - 16:42 #11
Og da 1/log(2) er en konstant er det netop O(log(n)) med en vilkårlig
logaritme.
Avatar billede backupmand Nybegynder
09. april 2001 - 21:25 #12
Hvordan skal O (log (n)) forstås?

Avatar billede stigc Nybegynder
09. april 2001 - 21:34 #13
O-notation ser på hvor mange gange funktionen skal kaldes baseret på n elementer.
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester