Skillnad mellan binär sökning och linjär sökning

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. Det söker efter ett angivet värde i en lista genom att markera 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. Binär sökmetod halverar antalet kontrollerade element (i varje iteration), vilket minskar tiden för att lokalisera det angivna 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 specificerat element. Inmatningen till den linjära sökmetoden är en sekvens (som en matris, samling eller en sträng) och objektet som behöver söks. Utsignalen är sann om det angivna objektet ligger inom den angivna sekvensen eller falsk om den inte finns i sekvensen. Eftersom denna metod 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 det nödvändiga elementet. Komplexiteten för linjär sökning är o (n). Därför anses det vara för långsamt att användas när man söker element i stora listor. Men det här är väldigt enkelt och lättare att genomföra.

Vad är binär sökning?

Binär sökning är också en metod som används för att lokalisera ett specificerat objekt i en sorterad lista. Denna metod börjar genom att jämföra det sökta elementet till elementen i mitten av listan. Om jämförelsen bestämmer att de två elementen är lika, stannar metoden och returnerar elementets läge. 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 det. Därför halverar binärsökmetoden antalet jämförda element (i varje iteration), beroende på resultatet av jämförelsen. Följaktligen kör binär sökning i logaritmisk tid vilket resulterar i o (log n) genomsnittliga 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 söker metoder har de flera skillnader. Medan binär sökning fungerar på sorterade listor kan linjesökning också användas på osorterade listor. Sortering av en lista har generellt en genomsnittskomplexitet av n log n. linjär sökning är enkel och enkel att implementera än binär sökning. 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 effektivare metod som kan användas med stora listor. Men genomförandet av binärsökning kan vara ganska knepigt och en studie har visat att den exakta koden för binär sökning kunde hittas i endast fem av tjugo böcker.