Innehåll

• Jämförelsediagram
• Definition av linjär sökning
• Definition av binär sökning
• Slutsats

Linjär sökning och binär sökning är de två metoderna som används i matriser för sökande elementen. Sökning är en process för att hitta ett element i listan över element lagrade i valfri ordning eller slumpmässigt.

Den största skillnaden mellan linjär sökning och binär sökning är att binär sökning tar mindre tid att söka efter ett element från den sorterade elementlistan. Så det dras slutsatsen att effektiviteten för binär sökningsmetod är större än linjär sökning.

En annan skillnad mellan de två är att det finns en förutsättning för den binära sökningen, dvs elementen måste vara sorterad medan det i linjär sökning inte finns någon sådan förutsättning. Även om båda sökmetoderna använder olika tekniker som diskuteras nedan.

1. Jämförelsediagram
2. Definition
3. Viktiga skillnader
4. Slutsats

Jämförelsediagram

Grund för jämförelse	Linjär sökning	Binär sökning
Tidskomplexitet	PÅ)	O (log 2 N)
Bästa fallet	Första element O (1)	Mittelement O (1)
Förutsättning för en matris	Ingen krävs	Array måste vara i sorterad ordning
Värsta fallet för N antal element	N jämförelser krävs	Kan avsluta efter bara logg2N jämförelser
Kan implementeras på	Array och länkad lista	Kan inte implementeras direkt på länkad lista
Sätt i drift	Enkelt infört i slutet av listan	Kräv bearbetning för att infoga på rätt plats för att behålla en sorterad lista.
Algoritmtyp	Iterativ i naturen	Dela och erövra i naturen
Användbarhet	Lätt att använda och inget behov av beställda element.	Hur som helst knepiga algoritmer och element bör organiseras i ordning.
Lines of Code	Mindre	Mer

Definition av linjär sökning

I en linjär sökning hämtas varje element i en matris en efter en i en logisk ordning och kontrolleras om det är önskat element eller inte. En sökning kommer inte att lyckas om alla element har åtkomst och det önskade elementet inte hittas. I värsta fall är antalet genomsnittliga fall vi kan skanna hälften av storleken på matrisen (n / 2).

Därför kan linjär sökning definieras som den teknik som går igenom matrisen i följd för att lokalisera det givna objektet. Programmet nedan illustrerar sökningen av ett element i matrisen med hjälp av sökning.

Effektivitet av linjär sökning

Tidsförbrukningen eller antalet jämförelser som gjorts vid sökning av en post i en söktabell avgör teknikens effektivitet. Om den önskade posten finns i den första positionen i söktabellen görs bara 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 är antalet jämförelser i genomsnitt (n + 1/2). Det värsta fallet med denna teknik är O (n) står för utföringsordningen.

C-program att söka i ett element med linjär sökteknik.

#inkludera #inkludera void main () {int a, n, i, item, loc = -1; clrscr (); f (" n Ange antalet element:"); scanf ("% d", & n); f ("Ange siffrorna: n"); för (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" n Ange numret som ska sökas:"); scanf ("% d", & artikel); för (i = 0; i <= n-1; i ++) {if (artikel == a) {loc = i; ha sönder; }} if (loc> = 0) {f (" n% d finns i position% d:", post, loc + 1); } else {f (" n Objektet finns inte"); } getch (); }

Definition av binär sökning

Binär sökning är en extremt effektiv algoritm. Denna sökteknik förbrukar mindre tid på att söka efter det givna objektet i minst möjliga jämförelser. För att göra den binära sökningen måste vi först sortera arrayelementen.

Logiken bakom denna teknik ges nedan:

• Hitta först det mellersta elementet i matrisen.
• Mittelementet i arrayen jämförs med elementet som ska sökas.

Det finns tre fall som kan uppstå:

1. Om elementet är det obligatoriska elementet är sökningen framgångsrik.
2. När elementet är mindre än önskat objekt söker du bara i den första halvan av matrisen.
3. 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 avgas i sökområdet. I denna algoritm minskar varje gång sökområdet. Därför är antalet jämförelser högst log (N + 1). Som ett resultat är det en effektiv algoritm i jämförelse med linjär sökning, men matrisen måste sorteras innan du gör den binära sökningen.

C-program för att hitta ett element med binär sökningsteknik.

#inkludera void main () {int i, beg, end, middle, n, search, array; f ("Ange antalet element n"); scanf ( "% d", & n); f ("Ange% d-siffrorna n", n); för (i = 0; i <n; i ++) scanf ("% d", & array); f ("Ange nummer som ska sökas n"); scanf ("% d", & search); tigga = 0; slut = n - 1; mitten = (beg + slut) / 2; medan (beg <= slut) {if (array <sökning) beg = mitt + 1; annars om (array == sök) {f ("Sökningen är framgångsrik. n% d hittades på plats% d. n", sökning, mitt + 1); ha sönder; } annat slut = mitten - 1; mitten = (beg + slut) / 2; } if (beg> slut) f ("Sökning misslyckas!% d är inte närvarande i listan. n", sök); getch (); }

1. Linjär sökning är iterativ till sin natur och använder sekventiell metod. Å andra sidan delar binärsökning uppdelning och erövring.
2. Tidskomplexiteten för linjär sökning är O (N) medan binär sökning har O (log₂N).
3. Det bästa fallet i linjär sökning är för det första elementet, dvs O (1). I motsats till, i binär sökning, är det för mellanelementet, dvs O (1).
4. I den linjära sökningen är det värsta fallet för att söka efter ett element ett N-jämförelse. Däremot är det logg₂N antal jämförelser för binär sökning.
5. Linjär sökning kan implementeras i både en grupp och i länkad lista medan binär sökning inte kan implementeras direkt på länkad lista.
6. Som vi vet kräver binär sökning den sorterade matrisen som är anledningen till att den kräver bearbetning för att infoga på sin rätt plats för att behålla en sorterad lista. Tvärtom kräver linjär sökning inte sorterade element, så element läggs enkelt in i slutet av listan.
7. Linjär sökning är enkel att använda och det finns inget behov av beställda element. Å andra sidan är binär sökalgoritm dock svårt, 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 matris är datastrukturen och elementen är ordnade i sorterad ordning föredras binär sökning snabbtsökande. Om länkad lista är datastrukturen oavsett hur elementen är arrangerade, antas linjär sökning på grund av otillgänglighet för direkt implementering av binär sökalgoritm.

Den typiska binära sökalgoritmen kan inte användas för länkad lista eftersom länkad lista är dynamisk och det är inte känt var mittelementet faktiskt tilldelas. Därför finns det ett krav att utforma variationen av den binära sökalgoritmen som kan fungera på länkad lista också eftersom den binära sökningen är snabbare i körning än en linjär sökning.