Binär sökning kontra linjär sökning
Linjär sökning, även känd som sekventiell sökning, är den enklaste sökalgoritmen. Den söker efter ett angivet värde i en lista genom att kontrollera varje element i listan. Binär sökning är också en metod som används för att hitta ett specificerat värde i en sorterad lista. Binär sökmetod halverar antalet kontrollerade element (i varje iteration), vilket minskar tiden det tar att hitta det givna objektet i listan.
Vad är linjär sökning?
Linjär sökning är den enklaste sökmetoden, som kontrollerar varje element i en lista sekventiellt tills det hittar ett specificerat element. Indata till den linjära sökmetoden är en sekvens (som en array, samling eller en sträng) och objektet som behöver sökas. Utdata är sant om det angivna objektet är inom den angivna sekvensen eller falskt om det inte finns i sekvensen. Eftersom denna metod kontrollerar varje objekt i listan tills det angivna objektet hittas, kommer den i värsta fall att gå igenom alla element i listan innan den hittar det nödvändiga elementet. Komplexiteten i linjär sökning är o(n). Därför anses den vara för långsam för att användas vid sökning av element i stora listor. Men det här är väldigt enkelt och lättare att implementera.
Vad är binär sökning?
Binär sökning är också en metod som används för att hitta ett specificerat objekt i en sorterad lista. Denna metod börjar med att jämföra det sökta elementet med elementen i mitten av listan. Om jämförelsen bestämmer att de två elementen är lika, stoppar metoden och returnerar elementets position. Om det sökta elementet är större än mittelementet, startar det metoden igen med endast den nedre halvan av den sorterade listan. Om det sökta elementet är mindre än mittelementet, startar det metoden igen med endast den övre halvan av den sorterade listan. Om det sökta elementet inte finns i listan kommer metoden att returnera ett unikt värde som indikerar det. Därför halverar den binära sökmetoden antalet jämförda element (i varje iteration), beroende på resultatet av jämförelsen. Följaktligen körs binär sökning i logaritmisk tid, vilket resulterar i o(log n) genomsnittlig fallprestanda.
Vad är skillnaden mellan binär sökning och linjär sökning?
Även om både linjär sökning och binär sökning är sökmetoder har de flera skillnader. Medan binär sökning fungerar på sorterade listor, kan linjesökning också fungera på osorterade listor. Att sortera en lista har i allmänhet en genomsnittlig fallkomplexitet på n log n. linjär sökning är enkel och okomplicerad att implementera än den binära sökningen. Men linjär sökning är för långsam för att användas med stora listor på grund av dess o(n) genomsnittliga fallprestanda. Å andra sidan anses binär sökning vara en mer effektiv metod som skulle kunna användas med stora listor. Men att implementera den binära sökningen kan vara ganska knepig och en studie har visat att den korrekta koden för binär sökning kunde hittas i endast fem av tjugo böcker.
