rednil behöver inte mer hjälp
rednil 28 – Fd. Medlem
Postad: 14 sep 2020 15:15 Redigerad: 14 sep 2020 15:18

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 28 – Fd. Medlem
Postad: 14 sep 2020 15:17
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?

Laguna 30471
Postad: 14 sep 2020 15:18

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. 

Yngve Online 40278 – Livehjälpare
Postad: 14 sep 2020 17:50

Det saknas information för att det ska gå att ge ett vettigt svar. Är elementen sorterade? Vet vi hur?

Laguna 30471
Postad: 14 sep 2020 17:56

"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.

Yngve Online 40278 – Livehjälpare
Postad: 14 sep 2020 18:04

Det står inget om att de är ordnade.

Laguna 30471
Postad: 14 sep 2020 18:15 Redigerad: 14 sep 2020 18:17
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.

rednil 28 – Fd. Medlem
Postad: 18 sep 2020 16:27

svaret belv 12

Yngve Online 40278 – Livehjälpare
Postad: 18 sep 2020 17:42

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.

jek7 35 – Fd. Medlem
Postad: 19 sep 2020 09:13

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?

Yngve Online 40278 – Livehjälpare
Postad: 19 sep 2020 11:34

Ja, det stämmer att det ska vara 12.

Jag vet inte hur jag tänkte, men fel blev det 😀

Svara
Close