Didžiausias skirtumas tarp tiesinės paieškos ir dvejetainės paieškos yra tas, kad dvejetainė paieška trunka mažiau laiko ieškant elemento iš rūšiuojamo elementų sąrašo. Taigi daroma išvada, kad dvejetainių paieškos metodų efektyvumas yra didesnis nei tiesinė paieška.
Kitas skirtumas tarp dviejų yra tas, kad yra būtina binarinės paieškos sąlyga, ty elementai turi būti rūšiuojami, o tiesinėje paieškoje nėra tokios prielaidos. Nors abu paieškos metodai naudoja skirtingus metodus, kurie aptariami toliau.
Palyginimo diagrama
| Palyginimo pagrindas | Linijinė paieška | Binarinė paieška |
|---|---|---|
| Laiko sudėtingumas | O (N) | O (log 2 N) |
| Geriausias atvejo laikas | Pirmasis elementas O (1) | Centro elementas O (1) |
| Reikalavimas masyvui | Nereikalaujama | Array turi būti rūšiuojama tvarka |
| Blogiausias N elementų skaičius | Reikalingi N palyginimai | Galima daryti išvadą tik po 2 N lyginimo |
| Galima įgyvendinti | Array ir susietas sąrašas | Negalima tiesiogiai įgyvendinti susietame sąraše |
| Įdėkite operaciją | Lengvai įterpiamas sąrašo pabaigoje | Reikalauti apdorojimo, kad būtų galima įterpti tinkamą vietą, kad būtų galima tvarkyti surūšiuotą sąrašą. |
| Algoritmo tipas | Iteracinis pobūdis | Padalinkite ir užkariaukite gamtoje |
| Naudingumas | Lengva naudoti ir nereikia jokių užsakytų elementų. | Bet kokiu atveju sudėtingas algoritmas ir elementai turėtų būti organizuoti. |
| Kodo eilutės | Mažiau | Daugiau |
Linijinės paieškos apibrėžimas
Linijinėje paieškoje kiekvienas masyvo elementas yra paimtas po vieną logine tvarka ir patikrinamas, ar jis yra pageidaujamas elementas, ar ne. Paieška bus nesėkminga, jei bus pasiekti visi elementai, o norimas elementas nerastas. Blogiausiu atveju vidutinis atvejis, kuriam gali tekti nuskaityti pusę matricos dydžio (n / 2).
Todėl tiesinė paieška gali būti apibrėžiama kaip technika, perkelianti masyvą nuosekliai tam, kad surastų nurodytą elementą. Toliau pateikta programa iliustruoja masyvo elemento paiešką naudojant paiešką.
Tiesinės paieškos efektyvumas
Laiko vartojimas arba palyginimų, atliktų ieškant įrašo paieškos lentelėje, skaičius nustato technikos efektyvumą. Jei pageidaujamas įrašas yra pirmos paieškos lentelės pozicijoje, tada atliekamas tik vienas palyginimas. Kai pageidaujamas įrašas yra paskutinis, reikia atlikti n palyginimus. Jei įrašas bus pateiktas kažkur paieškos lentelėje, palyginimų skaičius bus (n + 1/2). Blogiausias šio metodo efektyvumas yra O (n) reiškia vykdymo tvarką.
C Programa ieškoti elemento su tiesine paieškos technika.
#include #include void main () {int a [100], n, i, elementas, loc = -1; clrscr (); printf ("Įveskite elemento numerį"); scanf ("% d", ir n); printf ("Įveskite skaičius: n"); (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf („Įveskite ieškomą numerį:“); scanf ("% d", ir elementas); (i = 0; i = 0) {printf ("n% d randamas pozicijoje% d:", elementas, loc + 1); } else {printf („Nėra elemento“); } getch (); } Binarinės paieškos apibrėžimas
Binarinė paieška yra labai efektyvus algoritmas. Ši paieškos technika mažiau laiko praleidžia ieškodama tam tikro elemento kiek įmanoma mažiau palyginimų. Norėdami atlikti dvejetainę paiešką, pirmiausia turime surūšiuoti masyvo elementus.
Šios technikos logika pateikiama žemiau:
- Pirma, suraskite vidurinį masyvo elementą.
- Vidutinis masyvo elementas yra lyginamas su ieškomu elementu.
Gali būti trys atvejai:
- Jei elementas yra būtinas elementas, paieška sėkminga.
- Kai elementas yra mažesnis už norimą elementą, tada ieškokite tik pirmos masyvo pusės.
- Jei jis yra didesnis už norimą elementą, tada ieškokite antroje masyvo pusėje.
Pakartokite tuos pačius veiksmus, kol paieškos srityje randamas elementas arba išsekama. Šiame algoritme kiekvieną kartą paieškos sritis mažėja. Todėl palyginimų skaičius yra daugiausia log (N + 1). Kaip rezultatas, tai yra efektyvus algoritmas, lyginant su tiesine paieška, bet masyvas turi būti surūšiuotas prieš atliekant dvejetainę paiešką.
C Programa surasti elementą su dvejetainiu paieškos metodu.
#include void main () {int i, elgetavimas, pabaiga, vidurio, n, paieška, masyvas [100]; printf ("Įveskite elemento skaičių"); scanf ("% d", ir n); printf ("Įveskite% d skaičius n", n); (i = 0; i <n; i ++) scanf ("% d", ir masyvas [i]); printf („Įveskite ieškomą numerį“); scanf ("% d" ir paieška); beg = 0; pabaiga = n - 1; vidurinis = (elgetas + pabaiga) / 2; o (beg <= end) {if (array [middle] end) printf ("Paieška nepavyksta!% d nėra sąraše. \ t getch (); } Pagrindiniai skirtumai tarp tiesinės paieškos ir dvejetainės paieškos
- Linijinė paieška yra natūrali ir kartojasi. Kita vertus, dvejetainių paieškų sistema vykdo pasidalijimo ir užkariavimo metodą.
- Linijinės paieškos laiko sudėtingumas yra O (N), o binarinė paieška - O (log 2 N).
- Geriausias atvejo laikas tiesinėje paieškoje yra pirmasis elementas, ty O (1). Kaip ir binarinėje paieškoje, tai yra viduriniam elementui, ty O (1).
- Linijinėje paieškoje blogiausiu atveju ieškant elemento yra N palyginimo numeris. Atvirkščiai, tai yra log 2 N palyginimo skaičius dvejetaininei paieškai.
- Linijinę paiešką galima įgyvendinti masyve, taip pat susietame sąraše, o dvejetainė paieška negali būti vykdoma tiesiogiai susietame sąraše.
- Kaip žinome, pagal dvejetainį paiešką reikia surūšiuoti masyvą, kuris yra priežastis. Tam, kad būtų galima tvarkyti surūšiuotą sąrašą, reikia įterpti tinkamą vietą. Priešingai, tiesinė paieška nereikalauja surūšiuotų elementų, todėl elementai lengvai įterpiami sąrašo pabaigoje.
- Linijinė paieška yra paprasta naudoti, todėl nereikia jokių užsakytų elementų. Kita vertus, dvejetainio paieškos algoritmas vis dėlto yra sudėtingas, o elementai yra būtinai išdėstyti pagal tvarką.
Išvada
Tiek linijiniai, tiek dvejetainiai paieškos algoritmai gali būti naudingi, priklausomai nuo programos. Kai masyvas yra duomenų struktūra ir elementai yra išdėstyti pagal rūšiavimo tvarką, tada greitajai paieškai pageidaujama dvejetainė paieška. Jei susietas sąrašas yra duomenų struktūra, neatsižvelgiant į tai, kaip elementai yra išdėstyti, linijinė paieška priimama dėl to, kad nėra tiesioginio binarinės paieškos algoritmo įgyvendinimo.
Tipinis dvejetainio paieškos algoritmas negali būti naudojamas susietam sąrašui, nes susietas sąrašas yra dinamiškas ir nėra žinoma, kur iš tikrųjų priskiriamas vidutinis elementas. Taigi yra reikalavimas sukurti binarinės paieškos algoritmo variaciją, kuri taip pat gali veikti susietame sąraše, nes dvejetainė paieška yra greitesnė nei linijinė paieška.
