Den stora skillnaden mellan linjär sökning och binär sökning är att binär sökning tar mindre tid att söka ett element från den sorterade listan över element. Således är det slutsatsen att effektiviteten hos binär sökmetod är större än linjär sökning.
En annan skillnad mellan de två är att det finns en förutsättning för binär sökning, dvs elementen måste sorteras medan linjär sökning saknar sådan förutsättning. Även om båda sökmetoderna använder olika tekniker som diskuteras nedan.
Jämförelsediagram
| Grunder för jämförelse | Linjär sökning | Binär sökning |
|---|---|---|
| Tidskomplexitet | PÅ) | O (log 2 N) |
| Bästa fallet tid | Första elementet O (1) | Center Element O (1) |
| Förutsättning för en array | Nej krävs | Array måste vara i sorterad ordning |
| Värsta fallet för N antal element | N-jämförelser krävs | Kan sluta efter logga bara 2 N jämförelser |
| Kan genomföras på | Array och länklista | Kan inte implementeras direkt på länklistan |
| Sätt i funktionen | Enkelt in i slutet av listan | Kräver bearbetning för att infoga på rätt plats för att behålla en sorterad lista. |
| Algoritm typ | Iterativ i naturen | Dela och erövra i naturen |
| Användbarhet | Lätt att använda och inget behov av några beställda element. | Hur som helst, knepig algoritm och element bör organiseras i ordning. |
| Kodslinjer | Mindre | Mer |
Definition av linjär sökning
I en linjär sökning hämtas varje element i en array en efter en i en logisk ordning och kontrollerar om det är önskat element eller inte. En sökning kommer att misslyckas om alla element är tillgängliga och det önskade elementet hittas inte. I värsta fall kan antalet genomsnittliga fall vi behöva skanna hälften av arrayens storlek (n / 2).
Därför kan linjär sökning definieras som den teknik som traverserar matrisen i följd för att lokalisera det angivna objektet. Programmet som anges nedan illustrerar sökningen av ett element i arrayen med hjälp av sökning.
Effektivitet av linjär sökning
Tidskonsumtionen eller antalet jämförelser som gjorts för att söka en post i ett söktabell bestämmer effektiviteten hos tekniken. Om den önskade posten är närvarande i söktabellens första position, görs endast en jämförelse. När den önskade posten är den sista, måste n-jämförelser göras. Om posten ska presenteras någonstans i söktabellen, kommer i genomsnitt antalet jämförelser att vara (n + 1/2). Värsta effektiviteten i denna teknik är O (n) står för utföringsordningen.
C Program för att söka ett element med linjär sökteknik.
#include #include void main () {int a [100], n, i, objekt, loc = -1; clrscr (); printf ("\ nEngör antalet element:"); scanf ("% d", & n); printf ("Ange siffrorna: \ n"); för (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ n Ange numret som ska sökas:"); scanf ("% d", & post); för (i = 0; i = 0) {printf ("\ n% d finns i position% d:", objekt, loc + 1); } else {printf ("\ n Föremålet existerar inte"); } getch (); } Definition av binär sökning
Binär sökning är en extremt effektiv algoritm. Denna sökteknik förbrukar mindre tid när du söker efter det angivna objektet i minimala möjliga jämförelser. För att göra binärsökningen måste vi först sortera arrayelementen.
Logiken bakom denna teknik ges nedan:
- Först, hitta mittelementet i matrisen.
- Medelelementet i matrisen jämförs med det element som ska sökas.
Det kan uppstå tre fall:
- Om elementet är det nödvändiga elementet, är sökningen lyckad.
- När elementet är mindre än det önskade objektet, sök bara den första halvan av matrisen.
- Om det är större än det önskade elementet, sök sedan i den andra halvan av matrisen.
Upprepa samma steg tills ett element hittas eller avgaser i sökområdet. I denna algoritm reduceras varje gång sökområdet. Därför är antalet jämförelser högst logg (N + 1). Som ett resultat är det en effektiv algoritm jämfört med linjär sökning, men arrayen måste sorteras innan du gör binär sökning.
C Program för att hitta ett element med binär sökteknik.
#include void main () {int i, beg, slutet, mitten, n, sök, array [100]; printf ("Ange antal element \ n"); scanf ( "% d", & n); printf ("Ange% d nummer \ n", n); för (i = 0; i <n; i ++) scanf ("% d", & array [i]); printf ("Ange nummer som ska sökas \ n"); scanf ("% d", & sök); beg = 0; slutet = n - 1; mitten = (beg + slutet) / 2; medan (beg <= slutet) {om (array [middle] end) printf ("Sökningen misslyckas!% d finns inte i listan. \ n", sök); getch (); } Viktiga skillnader mellan linjär sökning och binär sökning
- Linjär sökning är iterativ i naturen och använder sekventiell tillvägagångssätt. Å andra sidan använder binära sökningar dela och erövra tillvägagångssätt.
- Tidskomplexiteten för linjär sökning är O (N) medan binär sökning har O (log 2 N).
- Den bästa fallstiden i linjär sökning är för det första elementet, dvs O (1). När det gäller binär sökning är det för mittelementet, dvs O (1).
- I den linjära sökningen är värsta fallet för att söka ett element N antal jämförelser. Däremot är det log 2 N antal jämförelse för binär sökning.
- Linjär sökning kan implementeras i en array såväl som i länkad lista medan binär sökning inte kan implementeras direkt på länkad lista.
- Som vi vet Binär sökning kräver den sorterade matrisen som är orsak. Det krävs att bearbetningen sätts in på rätt plats för att behålla en sorterad lista. Tvärtom kräver linjär sökning inte sorterade element, så element är enkelt införda i slutet av listan.
- Linjär sökning är lätt att använda, och det finns inget behov av några beställda element. Å andra sidan är binär sök algoritm dock knepigt, och element är nödvändigtvis ordnade i ordning.
Slutsats
Både linjära och binära sökalgoritmer kan vara användbara beroende på applikationen. När en array är datastrukturen och elementen är ordnade i sorterad ordning, föredras binär sökning för snabb sökning. Om länkad lista är datastrukturen oavsett hur elementen är ordnade antas linjär sökning på grund av otillgänglighet av direkt implementering av binär sökalgoritm.
Den typiska binära sökalgoritmen kan inte användas till länkad lista eftersom länklistan är dynamisk i naturen och det är inte känt där mellannementet faktiskt är tilldelat. Därför är det ett krav att utforma variationen i binärsökningsalgoritmen som kan fungera på länkad lista också eftersom binärsökningen är snabbare i utförande än en linjär sökning.
