Linjär sökning kontra binär sökning

Innehåll

Innehåll: Skillnaden mellan linjär sökning och binär sökning
Jämförelsediagram
Binär sökning
Viktiga skillnader
Slutsats
Förklarande video

Skillnaden mellan linjär sökning och en binär sökning är att i linjär sökning varje element kontrolleras och jämförs och sorteras sedan medan i binärsökning en lista som ska sorteras delas upp i två delar och sedan sorteras. Sökning och sortering är två huvudbegrepp inom datorprogrammering. Många algoritmer används för att söka och sortera, men de två mest använda algoritmerna för sökning och sortering är linjär sökning och binär sökning.

Skillnaden mellan den linjära sökningen och en binär sökning är funktionen och effektiviteten för båda algoritmerna. Binär sökning är en mycket effektivare algoritm jämfört med den linjära sökalgoritmen. Iterationen eller tiden det tar att jämföra varje värde innan sortering är mindre i binär sökning jämfört med linjär sökning.

Linjär sökning är en mycket komplex algoritm om du vill söka efter ett nummer i en lista, jämföra och upprepa ibland antalet värden i listan. Varje element i listan hämtas en efter en och jämförs med det intilliggande elementet. Alla element öppnas och kontrolleras och sedan hittas rätt element. Det kan vara värsta fall om det sista numret i listan är det nummer som ska sökas. Linjär sökning är den metod genom vilken matrisen går igenom och elementet som ska sökas grundas. Om vi talar om effektiviteten är effektiviteten antalet gånger programmet måste köra för att hitta antalet. Om vi hittar det nummer vi letar efter i den första positionen måste bara en jämförelse göras, och saker sorteras men om inte, måste jämförelser göras om och om igen, och minnet slösas bort. I genomsnitt är antalet jämförelser (n + 1/2). Och det värsta fallet med denna teknik är O (n) står för exekveringsordningen.

Jämfört med den linjära sökningen är binär sökning mycket effektiv. I denna metod är matrisen uppdelad i två delar och på detta sätt är antalet jämförelser mycket mindre jämfört med binär sökning. Tiden är också mindre i binär sökning jämfört med linjär sökning. Binärsökning fungerar på det sätt som mittenelementet i matrisen hittas och sedan jämförs det mellersta elementet med en del av matrisen. Det kan finnas tre möjligheter som är mittnummer kan vara det nummer vi behöver hitta eller antalet som är mindre än mittnumret eller antalet som är större än mitten av mittnumret. Antalet jämförelser är högst loggen (N + 1). Binär sökning jämfört med linjär sökning är en effektiv algoritm jämfört med linjär sökning, men matrisen måste sorteras innan du gör den binära sökningen.

Innehåll: Skillnaden mellan linjär sökning och binär sökning

Jämförelsediagram
Binär sökning
Viktiga skillnader
Slutsats
Förklarande video

Jämförelsediagram

Grund	Linjär sökning	Binär sökning
Menande	Linjär sökning varje element kontrolleras och jämförs och sorteras sedan	Binärsökning en lista som ska sorteras är uppdelad i två delar och sedan sorterad.
Tidskomplexitet	Tidskomplexiteten för den linjära sökningen är O (N).	Tidskomplexiteten för den binära sökningen är O (logg ₂ N)
Typ av algoritm	Linjär sökning är iterativ.	Binär sökning är splittring och erövring.
Rad med kod	I en linjär sökning måste vi skriva mer kod.	I en binär sökning måste vi skriva mindre kod.

Linjär sökning

Linjär sökning är en mycket komplex algoritm om du vill söka efter ett nummer i en lista, jämföra och upprepa vissa gånger antalet värden i listan. Varje element i listan hämtas en efter en och jämförs med det intilliggande elementet. Alla element öppnas och kontrolleras, och sedan hittas rätt element. Det kan vara värsta fall om det sista numret i listan är det nummer som ska sökas. Linjär sökning är den metod genom vilken matrisen går igenom och elementet som ska sökas grundas. Om vi talar om effektiviteten är effektiviteten antalet gånger programmet måste köra för att hitta antalet. Om vi hittar det nummer vi letar efter i den första positionen måste bara en jämförelse göras, och saker sorteras men om inte, måste jämförelser göras om och om igen, och minnet slösas bort. I genomsnitt är antalet jämförelser (n + 1/2). Och det värsta fallet med denna teknik är O (n) står för utföringsordningen.

Binär sökning

Jämfört med linjär sökning är binär sökning mycket effektiv. I denna metod är matrisen uppdelad i två delar och på detta sätt är antalet jämförelser mycket mindre jämfört med binär sökning. Tiden är också mindre i binär sökning jämfört med linjär sökning. Binärsökning fungerar på det sätt som det mellersta elementet i matrisen hittas och sedan jämförs det mellersta elementet med en del av matrisen.

Det kan finnas tre möjligheter som är mittnummer kan vara det nummer vi behöver hitta eller antalet som är mindre än mittnumret eller antalet som är större än mitten av mittnumret. Antalet jämförelser är högst loggen (N + 1). Binär sökning jämfört med linjär sökning är en effektiv algoritm jämfört med linjär sökning, men matrisen måste sorteras innan du gör den binära sökningen.

Viktiga skillnader

Linjär sökning varje element kontrolleras och jämförs och sorteras sedan medan binärsökning en lista som ska sorteras delas upp i två delar och sedan sorteras.
Tidskomplexiteten för linjär sökning är 0 (N) medan tidskomplexiteten för binär sökning är O (log₂N).
Linjär sökning är iterativ medan Binary search är splittring och erövring.
Vid linjär sökning måste vi skriva mer kod medan vi i binär sökning behöver skriva mindre kod.