Turinys

• Palyginimo diagrama
• Linijinės paieškos apibrėžimas
• Dvejetainės paieškos apibrėžimas
• Išvada

Linijinė paieška ir dvejetainė paieška yra du metodai, naudojami masyvuose ieškojimas elementai. Paieška - tai elementų, esančių bet kokia tvarka arba atsitiktine tvarka, sąrašo elementų paieška.

Pagrindinis skirtumas tarp linijinės ir dvejetainės paieškos yra tas, kad dvejetainė paieška užima mažiau laiko elemento paieškai išrūšiuotų elementų sąraše. Taigi daroma išvada, kad dvejetainės paieškos metodo efektyvumas yra didesnis nei tiesinės paieškos.

Kitas skirtumas tarp šių dviejų yra tas, kad yra būtina dvejetainės paieškos sąlyga, t.y., elementai turi būti rūšiuojami tuo tarpu linijinėje paieškoje tokios prielaidos nėra. Nors abu paieškos metodai naudoja skirtingus metodus, kurie aptariami toliau.

1. Palyginimo diagrama
2. Apibrėžimas
3. Pagrindiniai skirtumai
4. Išvada

Palyginimo diagrama

Palyginimo pagrindas	Linijinė paieška	Dvejetainė paieška
Laiko sudėtingumas	O (N)	O (žurnalas 2 N)
Geriausio atvejo laikas	Pirmasis elementas O (1)	Centro elementas O (1)
Būtina masyvo sąlyga	Nereikia	Masyvas turi būti surūšiuotas
Blogiausias N elementų skaičius	N lyginti nereikia	Gali padaryti išvadą tik prisijungęs2N palyginimų
Gali būti įdiegta	Masyvas ir susietų sąrašas	Neįmanoma tiesiogiai įgyvendinti susietame sąraše
Įdėkite operaciją	Lengvai įterpiamas sąrašo gale	Reikalaukite apdorojimo, kad įterptumėte tinkamoje vietoje, kad būtų tvarkomas rūšiuotas sąrašas.
Algoritmo tipas	Iteracinio pobūdžio	Padalinkite ir užkariaukite gamtoje
Naudingumas	Paprastas naudoti ir nereikia jokių užsakytų elementų.	Bet kokiu atveju sudėtingas algoritmas ir elementai turėtų būti išdėstyti tvarka.
Kodo eilutės	Mažiau	Daugiau

Linijinės paieškos apibrėžimas

Linijinėje paieškoje kiekvienas masyvo elementas yra paimamas po vieną logine tvarka ir patikrinama, ar tai norimas elementas, ar ne. Paieška bus nesėkminga, jei bus pasiekti visi elementai, o norimas elementas nerastas. Blogiausiu atveju vidutinio atvejo skaičių mums gali reikėti nuskaityti pusei masyvo dydžio (n / 2).

Todėl linijinę paiešką galima apibrėžti kaip techniką, kuria masyvas eina paeiliui tam, kad surastų duotą elementą. Žemiau pateikta programa iliustruoja masyvo elemento paiešką naudojant paiešką.

Efektyvumas linijinės paieškos

Laiko sąnaudos arba palyginimų, atliktų ieškant įrašo paieškos lentelėje, skaičius lemia technikos efektyvumą. Jei norimo įrašo yra pirmoje paieškos lentelės pozicijoje, atliekamas tik vienas palyginimas. Kai norimas įrašas yra paskutinis, tada reikia palyginti. Jei įrašas turi būti kažkur paieškos lentelėje, vidutiniškai palyginimų skaičius bus (n + 1/2). Blogiausias šios technologijos efektyvumas yra O (n) - vykdymo tvarka.

C programa ieškoti elemento su tiesine paieškos technika.

# įtraukti # įtraukti void main () {int a, n, i, item, loc = -1; clrscr (); f (" nĮveskite elemento skaičių:"); „scanf“ („% d“, & n); f ("Įveskite skaičius: n"); už (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" nĮveskite skaičių, kurio reikia ieškoti:"); „scanf“ („% d“, & elementas); už (i = 0; i <= n-1; i ++) {if (elementas == a) {loc = i; pertrauka; }} if (loc> = 0) {f (" n% d randamas% d pozicijoje:", elementas, loc + 1); } else {f (" n elemento nėra"); } getch (); }

Dvejetainės paieškos apibrėžimas

Dvejetainė paieška yra ypač efektyvus algoritmas. Ši paieškos technika sugaišta mažiau laiko ieškant nurodyto elemento kuo mažiau palyginimų. Pirmiausia, norėdami atlikti dvejetainę paiešką, turime surūšiuoti masyvo elementus.

Šios technikos logika pateikiama žemiau:

• Pirmiausia raskite vidurinį masyvo elementą.
• Vidurinis masyvo elementas lyginamas su ieškomu elementu.

Gali kilti trys atvejai:

1. Jei elementas yra būtinas elementas, tada paieška yra sėkminga.
2. Kai elemento yra mažiau nei norimas elementas, ieškokite tik pirmoje masyvo pusėje.
3. Jei jis yra didesnis nei pageidaujamas elementas, tada ieškokite antroje masyvo pusėje.

Pakartokite tuos pačius veiksmus, kol elementas bus rastas arba išeikvos paieškos srityje. Šiuo algoritmu kaskart sumažėja paieškos sritis. Todėl palyginimų skaičius yra daugiausiai loginis (N + 1). Dėl to tai yra efektyvus algoritmas, palyginti su linijine paieška, tačiau prieš atliekant dvejetainę paiešką, masyvas turi būti rūšiuojamas.

C programa rasti elementą naudojant dvejetainę paieškos techniką.

# įtraukti void main () {int i, elgetauti, pabaiga, vidurys, n, ieškoti, masyvas; f ("Įveskite elemento numerį n"); „scanf“ („% d“, & n); f ("Įveskite% d skaičius n", n); (i = 0; i <n; i ++) scanf („% d“, ir masyvas); f ("Įveskite ieškomą numerį n"); „scanf“ („% d“, & ieškoti); elgeta = 0; pabaiga = n - 1; vidurys = (elgetauti + pabaiga) / 2; while (beg <= end) {if (masyvas <search) beg = middle + 1; else if (masyvas == paieška) {f ("Paieška sėkminga. n% d rasta vietoje% d. n", paieška, viduryje + 1); pertrauka; } kita pabaiga = vidurys - 1; vidurys = (elgetauti + pabaiga) / 2; } if (beg> end) f ("Paieška nesėkminga!% d nėra sąraše. n", ieškokite); getch (); }

1. Linijinė paieška yra iteracinio pobūdžio ir naudoja nuoseklųjį metodą. Kita vertus, dvejetainė paieška įgyvendina dalijimosi ir užkariavimo metodą.
2. Linijinės paieškos laiko sudėtingumas yra O (N), o dvejetainėje paieškoje yra O (log₂N).
3. Geriausias atvejo laikas tiesinėje paieškoje yra pirmasis elementas, ty O (1). Dvejetainėje paieškoje jis skirtas viduriniajam elementui, t. Y. O (1).
4. Linijinėje paieškoje blogiausias elemento paieškos atvejis yra N palyginimų skaičius. Priešingai, tai yra žurnalas₂N dvejetainės paieškos palyginimo skaičius.
5. Linijinė paieška gali būti įgyvendinama tiek masyve, tiek susietame sąraše, tuo tarpu dvejetainė paieška negali būti įgyvendinta tiesiogiai susietame sąraše.
6. Kaip mes žinome, dvejetainėje paieškoje reikia surūšiuoti masyvą, kuris yra priežastis. Norint tvarkyti rūšiuotą sąrašą, reikia apdoroti, kad įterptų tinkamoje vietoje. Atvirkščiai, linijinei paieškai nereikia surūšiuotų elementų, todėl elementai lengvai įterpiami sąrašo pabaigoje.
7. Linijinę paiešką lengva naudoti ir nereikia jokių užsakytų elementų. Kita vertus, dvejetainis paieškos algoritmas yra sudėtingas, o elementai būtinai išdėstomi eilės tvarka.

Išvada

Priklausomai nuo programos, gali būti naudingi tiek tiesiniai, tiek dvejetainiai paieškos algoritmai. Kai masyvas yra duomenų struktūra, o elementai yra išdėstyti surūšiuota tvarka, tada pirmenybė teikiama dvejetainėms paieškoms greitaiieškojimas. Jei susietas sąrašas yra duomenų struktūra, neatsižvelgiant į tai, kaip elementai yra išdėstyti, linijinė paieška pasirenkama dėl to, kad dvejetainės paieškos algoritmas nėra tiesiogiai įgyvendinamas.

Tipinis dvejetainis paieškos algoritmas negali būti naudojamas susietajam sąrašui, nes susietas sąrašas yra dinamiško pobūdžio ir nežinoma, kur iš tikrųjų priskirtas vidurinis elementas. Taigi yra reikalavimas suprojektuoti dvejetainės paieškos algoritmo variantą, kuris gali veikti ir susietame sąraše, nes dvejetainė paieška vykdoma greičiau nei linijinė paieška.