09. april 2001 - 00:21Der 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\");
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.
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.
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.
O-notation ser på hvor mange gange funktionen skal kaldes baseret på n elementer.
Synes godt om
Ny brugerNybegynder
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.