Innhold

• Sammenligningstabell
• Definisjon av lineært søk
• Definisjon av binært søk
• Konklusjon

Lineært søk og binært søk er de to metodene som brukes i matriser for søker elementene. Søke er en prosess for å finne et element i listen over elementer som er lagret i en hvilken som helst rekkefølge eller tilfeldig.

Den største forskjellen mellom lineært søk og binært søk er at binært søk tar mindre tid å søke i et element fra den sorterte listen over elementer. Så det utledes at effektiviteten til binær søkemetode er større enn lineært søk.

En annen forskjell mellom de to er at det er en forutsetning for det binære søket, dvs. elementene må være sorterte mens det i lineær søk ikke er noen slik forutsetning. Selv om begge søkemetodene bruker forskjellige teknikker som er diskutert nedenfor.

1. Sammenligningstabell
2. Definisjon
3. Viktige forskjeller
4. Konklusjon

Sammenligningstabell

Grunnlag for sammenligning	Lineært søk	Binærsøk
Tidskompleksitet	PÅ)	O (log 2 N)
Beste sakstid	Første element O (1)	Senterelement O (1)
Forutsetning for en matrise	Ingen påkrevd	Array må være i sortert rekkefølge
Verste tilfelle for N antall elementer	Det er ikke nødvendig med sammenligninger	Kan konkludere etter bare logg2N sammenligning
Kan implementeres på	Array og koblet liste	Kan ikke implementeres direkte på lenket liste
Sett inn betjening	Settes enkelt inn på slutten av listen	Krev behandling for å sette inn på rett sted for å opprettholde en sortert liste.
Algoritmetype	Iterativ i naturen	Del og erobre i naturen
nytten	Enkel å bruke og ikke behov for noen bestilte elementer.	Uansett bør vanskelige algoritmer og elementer organiseres i rekkefølge.
Lines of Code	Mindre	Mer

Definisjon av lineært søk

I et lineært søk blir hvert element i en matrise hentet ett etter ett i en logisk rekkefølge og sjekket om det er ønsket element eller ikke. Et søk vil ikke lykkes hvis alle elementene er tilgjengelige, og ønsket element ikke blir funnet. I verste fall kan antallet et gjennomsnittlig tilfelle vi måtte skanne halvparten av størrelsen på matrisen (n / 2).

Derfor kan lineært søk defineres som teknikken som går gjennom rekkefølgen sekvensielt for å lokalisere det gitte elementet. Programmet gitt nedenfor illustrerer søkingen av et element i matrisen ved hjelp av søk.

Effektivitet av lineært søk

Tidsforbruket eller antall sammenligninger som er gjort når du søker i en post i en søketabell, bestemmer teknikkens effektivitet. Hvis ønsket post er til stede i den første posisjonen i søketabellen, blir bare en sammenligning foretatt. Når ønsket post er den siste, må det gjøres n sammenligninger. Hvis posten skal vises et sted i søketabellen, i gjennomsnitt, vil antall sammenligninger være (n + 1/2). I verste fall er effektiviteten til denne teknikken O (n) for utførelsesrekkefølgen.

C-program å søke i et element med lineær søketeknikk.

#inkludere #inkludere void main () {int a, n, i, item, loc = -1; clrscr (); f (" n Skriv inn antall element:"); scanf ("% d", & n); f ("Tast inn tallene: n"); for (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" nTast inn nummeret som skal søkes:"); scanf ("% d", & vare); for (i = 0; i <= n-1; i ++) {if (item == a) {loc = i; gå i stykker; }} if (loc> = 0) {f (" n% d er funnet i posisjon% d:", post, loc + 1); } else {f (" n Varen eksisterer ikke"); } getch (); }

Definisjon av binært søk

Binærsøk er en ekstremt effektiv algoritme. Denne søketeknikken bruker mindre tid på å søke etter den gitte varen i minst mulig sammenligning. For å gjøre det binære søket, må vi først sortere matriseelementene.

Logikken bak denne teknikken er gitt nedenfor:

• Finn først det midtre elementet i matrisen.
• Det midtre elementet i matrisen sammenlignes med elementet som skal søkes.

Det er tre tilfeller som kan oppstå:

1. Hvis elementet er det nødvendige elementet, er søket vellykket.
2. Når elementet er mindre enn ønsket element, må du bare søke i første halvdel av matrisen.
3. Hvis det er større enn ønsket element, kan du søke i andre halvdel av matrisen.

Gjenta de samme trinnene til et element blir funnet eller tømmes i søkeområdet. I denne algoritmen reduseres hver gang søkeområdet. Derfor er antall sammenligninger på det meste logg (N + 1). Som et resultat er det en effektiv algoritme sammenlignet med lineært søk, men matrisen må sorteres før du gjør det binære søket.

C-program å finne et element med binær søketeknikk.

#inkludere void main () {int i, beg, end, middle, n, search, array; f ("Angi antall element n"); scanf ( "% d", og n); f ("Skriv inn% d tallene n", n); for (i = 0; i <n; i ++) scanf ("% d", & array); f ("Tast inn nummer som skal søkes n"); scanf ("% d", & søk); tigge = 0; slutt = n - 1; midten = (begynnelse + slutt) / 2; mens (beg <= slutt) {if (matrise <søk) beg = midten + 1; ellers hvis (matrise == søk) {f ("Søket er vellykket. n% d funnet på stedet% d. n", søk, midt + 1); gå i stykker; } annet slutt = midten - 1; midten = (begynnelse + slutt) / 2; } if (beg> slutt) f ("Søk mislykkes!% d er ikke til stede i listen. n", søk); getch (); }

1. Lineært søk er iterativt og bruker sekvensiell tilnærming. På den annen side, binære søk implementerer dele og erobre tilnærming.
2. Tidskompleksiteten til lineært søk er O (N) mens binært søk har O (log₂N).
3. Det beste tilfellet for lineært søk er for det første elementet, dvs. O (1). I motsetning til i binært søk er det for det midtre elementet, dvs. O (1).
4. I det lineære søket er det verste antall for å søke i et element N antall sammenligninger. I kontrast er det logg₂N antall sammenligninger for binært søk.
5. Lineært søk kan implementeres i en rekke så vel som i lenket liste, mens binært søk ikke kan implementeres direkte på lenket liste.
6. Som vi vet, krever binært søk det sorterte arrayet som er grunnen. Det krever behandling for å sette inn på sitt rette sted for å opprettholde en sortert liste. Tvert imot krever lineær søk ikke sorterte elementer, så elementer blir enkelt satt inn på slutten av listen.
7. Lineært søk er enkelt å bruke, og det er ikke behov for noen bestilte elementer. På den annen side er binær søkealgoritme imidlertid vanskelig, og elementer er nødvendigvis ordnet i rekkefølge.

Konklusjon

Både lineære og binære søkealgoritmer kan være nyttige avhengig av applikasjonen. Når en matrise er datastrukturen og elementene er ordnet i sortert rekkefølge, foretrekkes binært søk rasksøker. Hvis koblet liste er datastrukturen uansett hvordan elementene er ordnet, blir lineært søk vedtatt på grunn av utilgjengelighet av direkte implementering av binær søkealgoritme.

Den typiske binære søkealgoritmen kan ikke brukes til koblet liste fordi koblet liste er dynamisk og det er ikke kjent hvor midtelementet faktisk er tilordnet. Derfor er det et krav å utforme variasjonen av den binære søkealgoritmen som kan fungere på koblet liste også fordi det binære søket er raskere i utførelse enn et lineært søk.