Peamine erinevus lineaarse otsingu ja binaarse otsingu vahel on see, et binaarne otsing võtab elementide otsimiseks loendisse elementide nimekirjast vähem aega. Seega järeldatakse, et binaarse otsingu meetodi efektiivsus on suurem kui lineaarne otsing.
Teine erinevus nende kahe vahel on see, et binaarotsingul on eeltingimus, st elemendid tuleb sorteerida, samas kui lineaarses otsingus sellist eeldust ei ole. Kuigi mõlemad otsingumeetodid kasutavad erinevaid tehnikaid, mida allpool käsitletakse.
Võrdluskaart
| Võrdluse alus | Lineaarne otsing | Binaarne otsing |
|---|---|---|
| Aja keerukus | O (N) | O (log 2 N) |
| Parim juhtum | Esimene element O (1) | Keskelement O (1) |
| Massiivi eeldus | Ei ole vaja | Array peab olema järjestatud järjekorras |
| Kõige hullem N elementide arv | N võrdlusi on vaja | Võib järeldada pärast ainult log 2 N võrdlusi |
| Saab rakendada | Array ja Linked loend | Lingitud nimekirjas ei saa seda otse rakendada |
| Sisestage operatsioon | Lihtsalt lisada nimekirja lõppu | Nõuda töötlemist, et sisestada oma õigesse kohta sortitud nimekirja säilitamiseks. |
| Algoritmi tüüp | Looduslik iseloom | Jagada ja vallutada looduses |
| Kasulikkus | Lihtne kasutada ja ei ole vaja tellitud elemente. | Igatahes peaks keeruline algoritm ja elemendid olema järjestatud. |
| Koodide read | Vähem | Veel |
Lineaarse otsingu määratlus
Lineaarses otsingus leitakse iga massiivi ükshaaval loogilises järjekorras ja kontrollitakse, kas see on soovitud element või mitte. Otsing on ebaõnnestunud, kui kõik elemendid on kättesaadavad ja soovitud elementi ei leitud. Halvimal juhul võib keskmist juhtumit arvata, et skaneerida pool massiivi suurusest (n / 2).
Seetõttu saab lineaarset otsingut defineerida kui tehnikat, mis liigub massiivi järjestikku antud elemendi leidmiseks. Allpool toodud programm illustreerib massiivi elemendi otsingut otsingu abil.
Lineaarse otsingu tõhusus
Ajakulu või otsingu tabelis otsingu käigus tehtud võrdluste arv määrab tehnika tõhususe. Kui soovitud tabel asub otsingu tabeli esimesel positsioonil, siis tehakse ainult üks võrdlus. Kui soovitud rekord on viimane, tuleb teha n võrdlusi. Kui rekord peab esitlema kusagil otsingu tabelis, on võrdluste arv (n + 1/2). Selle meetodi halvim efektiivsus on O (n) tähistab täitmise järjekorda.
C Lineaarse otsingu tehnikaga elemendi otsingu programm.
#include #include void main () {int a [100], n, i, element, loc = -1; clrscr (); printf ("Sisestage elemendi arv:"); scanf ("% d", & n); printf ("Sisestage numbrid: n"); (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("Sisestage otsitav number:"); scanf ("% d", & üksus); (i = 0; i = 0) puhul {printf ("n% d leitakse positsioonis% d:", kirje, loc + 1); } else {printf ("Punkt ei ole olemas"); } getch (); } Binaarse otsingu määratlus
Binaarne otsing on äärmiselt tõhus algoritm. See otsingumeetod tarbib antud elemendi otsimisel võimalikult vähe aega võimalikult väikestes võrdlustes. Binaarotsingu tegemiseks peame esmalt sorteerima massiivi elemendid.
Selle tehnika loogika on toodud allpool:
- Esmalt leidke massiivi keskmine element.
- Massiivi keskmist elementi võrreldakse otsitava elemendiga.
Võib tekkida kolm juhtumit:
- Kui element on nõutav element, siis otsing on edukas.
- Kui element on soovitud üksusest väiksem, otsige ainult massiivi esimest poolt.
- Kui see on soovitud elemendist suurem, otsige massiivi teisel poolel.
Korrake samu samme, kuni leidub otsingupiirkonnas element või heitgaasid. Selles algoritmis väheneb iga kord otsingupiirkond. Seetõttu on võrdluste arv kõige rohkem log (N + 1). Selle tulemusena on see lineaarse otsinguga võrreldes tõhus algoritm, kuid massiiv tuleb sorteerida enne binaarotsingu tegemist.
C Programmeerige binaarse otsingu tehnikaga elemendi leidmiseks.
#include void main () {int i, kerjama, lõpus, keskel, n, otsing, massiiv [100]; printf ("Sisestage elemendi number"); scanf ("% d", & n); printf ("Sisestage% d numbrid n", n); (i = 0; i <n; i ++) jaoks scanf ("% d", & array [i]); printf ("Sisestage otsitav number"); scanf ("% d" ja otsing); beg = 0; end = n - 1; keskmine = (algus + lõpp) / 2; samal ajal (kerige <= lõpp) {if (massiivi [keskosa] lõpp) printf ("Otsing ei õnnestu!% d ei ole nimekirjas. \ t getch (); } Peamised erinevused lineaarse otsingu ja binaarse otsingu vahel
- Lineaarne otsing on laadi iteratiivne ja kasutab järjestikust lähenemist. Teisest küljest rakendab binaarotsing jagavat ja vallutavat lähenemist.
- Lineaarse otsingu aja keerukus on O (N), samas kui binaarotsingul on O (log 2 N).
- Lineaarse otsingu parim aeg on esimese elemendi, st O (1) puhul. Seevastu binaarsel otsingul on see keskelement, st O (1).
- Lineaarses otsingus on elemendi otsingu halvim juhtum võrdluse N arv. Seevastu on binaarseks otsinguks võrdluse log 2 N arv.
- Lineaarseid otsinguid saab rakendada nii massiivis kui ka lingitud nimekirjas, samas kui binaarotsingut ei saa otseselt seotud loendis kasutada.
- Nagu me teame, nõuab binaarne otsing sorteeritud massiivi, mis on põhjus See nõuab töötlemist, et sisestada oma õigesse kohta sortitud nimekirja säilitamiseks. Vastupidi, lineaarne otsing ei vaja sorteeritud elemente, mistõttu elemendid on loendi lõpus kergesti sisestatud.
- Lineaarne otsing on lihtne kasutada ja tellitud elemente ei ole vaja. Teisest küljest on binaarse otsingu algoritm siiski keeruline ja elemendid on tingimata järjestatud.
Järeldus
Sõltuvalt rakendusest võivad olla kasulikud nii lineaarsed kui ka binaarsed otsingu algoritmid. Kui massiiv on andmestruktuur ja elemendid on paigutatud järjestatud järjekorras, siis eelistatakse kiirotsinguks binaarset otsingut. Kui seotud nimekiri on andmestruktuur, olenemata sellest, kuidas elemendid on paigutatud, võetakse lineaarne otsing binaarse otsingu algoritmi otsese rakendamise puudumise tõttu.
Tüüpilist binaarset otsingu algoritmi ei saa kasutada lingitud nimekirjas, sest seotud nimekiri on looduses dünaamiline ja ei ole teada, kus keskelement on tegelikult määratud. Seega on nõue kujundada ka binaarse otsingu algoritmi variatsioon, mis võib toimida ka seotud nimekirjas, sest binaarne otsing on teostamisel kiirem kui lineaarne otsing.
