Binär sökningsalgoritm
Frågan är:
Vilket är det största antalet element (worst case) som kommer att undersökas om man gör en binär sökning på 4000 namn (element)?
Den börjar med att kolla om talet är 2000 annars inriktar den sig på höger eller vänster "sida" om 2000 och gör om processen tills den hittar talet? Så vad är största antalet som undersöks?
rednil skrev:Frågan är:
Vilket är det största antalet element (worst case) som kommer att undersökas om man gör en binär sökning på 4000 namn (element)?
Den börjar med att kolla om talet är 2000 annars inriktar den sig på höger eller vänster "sida" om 2000 och gör om processen tills den hittar talet? Så vad är största antalet som undersöks? 3?
Eller räknas 2000 som ett element och sedan 1000 som ett element osv?
Anta att det du söker efter är det första namnet. Hur ofta måste du halvera intervallen för att bara det ska vara kvar? Prova, det blir inte så farligt många.
Det saknas information för att det ska gå att ge ett vettigt svar. Är elementen sorterade? Vet vi hur?
"Element" är den generella termen för det som ligger i tabellen. De har valt namn som exempel, men det kan vara vad som helst. Det finns alltså 4000 element.
Det står inget om att de är ordnade.
Yngve skrev:Det står inget om att de är ordnade.
Det är väl det "worst-case" antyder.
Edit: nu tänkte jag fel. Om det är binärsökning måste de vara ordnade, annars kan man inte göra en binärsökning.
svaret belv 12
Med tänket "max otur" får jag det till 13 (no pun intended).
Men om vi vet att elementet finns i mängden så räcker det med 12 undersökningar.
Man kan kolla upp till x item med n sökningar enligt x=2^n-1 där ^ betyder upphöjt till. 2^12-1=4095. Exempel med n=4, x=15:
1:Kolla mittersta av 15 (7+1+7), så vet man vilken av 7 på var sida det är. 2:kolla mittersta igen så har man 3 kvar. 3: kolla mitten få en kvar. 4: kolla om den träffar, annars saknas det sökta. För x=4000 blir stegen 4000, 2000, 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1.
När man kollar mittersta, och (då det är worst case) den inte matchar, så försvinner ju den som kandidat, så det är (x-1)/2 och inte x/2 kvar att leta bland. Om man bara halverar (4000, 2000, 1000, 500, 250, 125, 63, 32, 16, 8, 4, 2, 1) verkar det bli 13 kollar, kanske så du Yngve råkade göra?
Ja, det stämmer att det ska vara 12.
Jag vet inte hur jag tänkte, men fel blev det 😀
