- Mål
- Fortfarande möjliga
- Jämförda
- Uteslutna
- Hittade
Binärsökning
Binärsökning hittar ett värde i en sorterad lista genom att alltid titta i mitten. Är mittvärdet för litet kan det sökta värdet bara komma efter det; är det för stort, bara före. Hur som helst utesluts hälften av det som är kvar. Välj värdet att söka efter, stega genom sökningen och se det skuggade området krympa tills värdet är hittat eller inget finns kvar. Tryck på Spela för att se sökningen, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa vart som helst. Den streckade linjen visar värdet du söker, och det skuggade området är där det fortfarande kan finnas. Binärsökning kräver en sorterad lista, så en osorterad lista sorteras först. Välj värdet, hur många staplar, eller skriv dina egna tal. När tavlan är markerad stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.
Hur det fungerar
- Välj värdet att söka efter och hur många staplar. Eller skriv dina egna tal: binärsökning sorterar dem först.
- Tryck på Spela, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst i sökningen.
- Jämför rutan Jämförelser med Linjär sökning skulle behöva, för ett värde nära slutet eller ett som saknas.
Så fungerar binärsökning
Håll reda på den del av den sorterade listan som fortfarande kan innehålla det sökta värdet; först är det hela listan. Titta på värdet i dess mitt. Är det lika med det sökta värdet är du klar. Är det mindre kan det sökta värdet bara komma efter, så fortsätt med delen efter mitten. Är det större, fortsätt med delen före. När inget finns kvar finns det sökta värdet inte i listan.
Varför den är så snabb
Varje jämförelse halverar den del som är kvar. Med n värden från början återstår efter k jämförelser högst ungefär n/2ᵏ, så sökningen slutar efter högst ⌊log₂ n⌋ + 1 jämförelser: 6 för 40 värden, 10 för 1 000, 20 för en miljon. Linjär sökning kan behöva titta på varje värde. Haken är att listan måste vara sorterad, och att hålla den sorterad, eller sortera den först, har sin egen kostnad.
Ofta ställda frågor
Hur fungerar binärsökning?
Den jämför det sökta värdet med mittvärdet i den del av en sorterad lista som fortfarande kan innehålla det. Lika betyder hittat; annars stryks den halva som inte kan innehålla värdet, och sökningen fortsätter i den andra halvan tills värdet är hittat eller inget finns kvar.
Hur många jämförelser behöver binärsökning?
Högst ⌊log₂ n⌋ + 1 för en lista med n värden: 6 för 40, 10 för 1 000, 20 för en miljon. Varje jämförelse halverar det som är kvar.
Varför kräver binärsökning en sorterad lista?
För att det bara är i en sorterad lista som en jämförelse säger vilken sida det sökta värdet ligger på. I en osorterad lista säger ett mindre värde i mitten ingenting om var det sökta värdet finns, så inget kan uteslutas.
Vilket värde hittas när det finns dubbletter?
Vilket som helst av dem, beroende på var mittpunkterna hamnar. Varianter som fortsätter söka åt vänster eller höger efter en träff hittar den första eller den sista förekomsten.
Skickas mina tal någonstans?
Nej. Sökningen körs i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor