Binär sökning vs 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 specificerat 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 lokalisera ett angivet värde i en sorterad lista. Metoden för binär sökning halverar antalet kontrollerade element (i varje iteration), vilket minskar den tid det tar att hitta det aktuella 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 i följd tills den hittar ett angivet element. Inmatningen till den linjära sökmetoden är en sekvens (som en matris, samling eller en sträng) och det objekt som behöver sökas. Utgången är sann om det angivna objektet ligger inom den angivna sekvensen eller falskt om det inte finns i sekvensen. Eftersom den här metoden kontrollerar varje objekt i listan tills det angivna objektet hittas, kommer det i värsta fall att gå igenom alla element i listan innan det hittar önskat element. Komplexiteten i linjär sökning är o (n). Därför anses det vara för långsamt för att användas när man söker efter element i stora listor. Men detta ä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 lokalisera ett angivet 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 fastställer att de två elementen är lika stannar metoden och returnerar elementets position. Om det sökta elementet är större än mittelementet startar metoden igen med endast den nedre halvan av den sorterade listan. Om det sökta elementet är mindre än mittelementet startar metoden igen med endast den övre halvan av den sorterade listan. Om det sökta elementet inte finns i listan returnerar metoden ett unikt värde som indikerar att. 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,binär sökning körs 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 enkel 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 kan användas med stora listor. Men att implementera den binära sökningen kan vara ganska knepig och en studie har visat att den exakta koden för binär sökning bara finns i fem av tjugo böcker.
