Prieš suprasdami skirtumus tarp linijinės ir dvejetainės paieškos, pirmiausia turėtume žinoti linijinę ir dvejetainę paiešką atskirai.

Kas yra linijinė paieška?

Linijinė paieška taip pat žinoma kaip nuosekli paieška, kuri tiesiog nuskaito kiekvieną elementą vienu metu. Tarkime, kad norime ieškoti elemento masyve arba sąraše; tiesiog apskaičiuojame jo ilgį ir nešokame prie jokio daikto.

Panagrinėkime paprastą pavyzdį.

Tarkime, kad turime 10 elementų masyvą, kaip parodyta toliau pateiktame paveikslėlyje:

Aukščiau pateiktame paveikslėlyje parodytas simbolių tipų masyvas, turintis 10 reikšmių. Jei norime ieškoti „E“, tada paieška pradedama nuo 0^thelementą ir nuskaito kiekvieną elementą, kol elementas, t. y. „E“, nerastas. Negalime tiesiogiai iššokti iš 0^thelementas į 4^thelementas, ty kiekvienas elementas yra nuskaitomas po vieną, kol elementas nerandamas.

Linijinės paieškos sudėtingumas

Kadangi linijinė paieška nuskaito kiekvieną elementą po vieną, kol elementas nerandamas. Jei elementų skaičius didėja, taip pat padidinamas ir nuskaitomų elementų skaičius. Galime pasakyti, kad laikas, per kurį reikia ieškoti elementų, yra proporcingas elementų skaičiui . Todėl blogiausio atvejo sudėtingumas yra O (n)

Kas yra dvejetainė paieška?

Dvejetainė paieška – tai paieška, kurios metu apskaičiuojamas vidurinis elementas, siekiant patikrinti, ar jis mažesnis ar didesnis nei ieškomas elementas. Pagrindinis dvejetainės paieškos pranašumas yra tai, kad ji nenuskaito kiekvieno sąrašo elemento. Užuot nuskaitęs kiekvieną elementą, jis atlieka paiešką iki pusės sąrašo. Taigi dvejetainė paieška užtrunka mažiau laiko elemento paieškai, palyginti su linijine paieška.

Vienas būtina dvejetainės paieškos sąlyga yra tai, kad masyvas turi būti surūšiuotas, o tiesinė paieška veikia tiek surūšiuotame, tiek nerūšiuotame masyve. Dvejetainis paieškos algoritmas yra pagrįstas padalijimo ir užkariauk technika, o tai reiškia, kad jis rekursyviai padalins masyvą.

Dvejetainėje paieškoje naudojami trys atvejai:

1 atvejis: duomenys

2 atvejis: duomenys>a[vidutinis], tada dešinėn = vidurys-1

3 atvejis: data = a[mid] // elementas rastas

Pirmiau nurodytu atveju ' a “ yra masyvo pavadinimas, vidurio yra elemento indeksas, apskaičiuotas rekursyviai, duomenis yra elementas, kurio reikia ieškoti, paliko žymi kairįjį masyvo elementą ir teisingai žymi elementą, esantį dešinėje masyvo pusėje.

Supraskime dvejetainės paieškos veikimą per pavyzdį.

Tarkime, kad turime 10 dydžio masyvą, indeksuotą nuo 0 iki 9, kaip parodyta toliau pateiktame paveikslėlyje:

Mes norime ieškoti 70 elementų iš aukščiau pateikto masyvo.

1 žingsnis: Pirmiausia apskaičiuojame vidurinį masyvo elementą. Mes atsižvelgiame į du kintamuosius, ty kairę ir dešinę. Iš pradžių kairėje = ​​0 ir dešinėje = ​​9, kaip parodyta toliau pateiktame paveikslėlyje:

Vidurinio elemento vertę galima apskaičiuoti taip:

Todėl mid = 4 ir a[mid] = 50. Ieškomas elementas yra 70, taigi a[mid] nėra lygus duomenims. 2 atvejis yra patenkintas, ty data>a[mid].

2 žingsnis: Kaip duomenys>a[vidutinis], taigi kairės reikšmė didinama mid+1, t.y. left=mid+1. Vidurio reikšmė yra 4, taigi kairės reikšmė tampa 5. Dabar turime posistemę, kaip parodyta toliau pateiktame paveikslėlyje:

Dabar vėlgi, vidutinė vertė apskaičiuojama naudojant aukščiau pateiktą formulę, o vidurio reikšmė tampa 7. Dabar vidurį galima pavaizduoti kaip:

Aukščiau pateiktame paveikslėlyje galime pastebėti, kad a[mid]>duomenys, taigi vėlgi, kitame žingsnyje bus apskaičiuojama vidurio reikšmė.

3 veiksmas: Remiantis [mid]> duomenimis, teisės vertė sumažinama iki 1 vidurio. Vidurio reikšmė yra 7, taigi dešinės reikšmė tampa 6. Masyvas gali būti pavaizduotas taip:

Vidurio reikšmė bus skaičiuojama dar kartą. Kairės ir dešinės reikšmės yra atitinkamai 5 ir 6. Todėl vidurio reikšmė yra 5. Dabar vidurį galima pavaizduoti masyve, kaip parodyta toliau:

Aukščiau pateiktame paveikslėlyje galime pastebėti, kad a[vid]

4 veiksmas: Kaip [viduryje]

Dabar vidurio reikšmė vėl apskaičiuojama pagal formulę, kurią jau aptarėme. Kairės ir dešinės reikšmės yra atitinkamai 6 ir 6, todėl vidurio reikšmė tampa 6, kaip parodyta toliau pateiktame paveikslėlyje:

Aukščiau pateiktame paveikslėlyje galime pastebėti, kad a[mid]=duomenys. Todėl paieška baigta ir elementas sėkmingai rastas.

Linijinės ir dvejetainės paieškos skirtumai

Toliau pateikiami linijinės ir dvejetainės paieškos skirtumai:

apibūdinimas

Linijinė paieška – tai paieška, kurios metu elementas randamas sąraše ieškant elemento nuosekliai, kol elementas randamas sąraše. Kita vertus, dvejetainė paieška yra paieška, kuri rekursyviai randa vidurinį sąrašo elementą, kol vidurinis elementas bus suderintas su ieškomu elementu.

Abiejų paieškų veikimas

Linijinė paieška pradeda paiešką nuo pirmojo elemento ir nuskaito po vieną elementą neperšokdama prie kito elemento. Kita vertus, dvejetainė paieška padalija masyvą į pusę, apskaičiuodama vidurinį masyvo elementą.

Įgyvendinimas

Linijinę paiešką galima įgyvendinti bet kurioje linijinėje duomenų struktūroje, pvz., vektoriuje, atskirai susietame sąraše, dvigubai susietame sąraše. Priešingai, dvejetainė paieška gali būti įgyvendinta tose duomenų struktūrose, kuriose yra dvipusis judėjimas, ty pirmyn ir atgal.

Sudėtingumas

Linijinę paiešką lengva naudoti arba galime sakyti, kad ji ne tokia sudėtinga, nes linijinės paieškos elementai gali būti išdėstyti bet kokia tvarka, o dvejetainėje paieškoje elementai turi būti išdėstyti tam tikra tvarka.

Surūšiuoti elementai

Linijinės paieškos elementai gali būti išdėstyti atsitiktine tvarka. Tiesinėje paieškoje nėra privaloma, kad elementai būtų išdėstyti rūšiuota tvarka. Kita vertus, atliekant dvejetainę paiešką, elementai turi būti išdėstyti rūšiuota tvarka. Jis gali būti išdėstytas didėjančia arba mažėjančia tvarka, todėl algoritmas bus atitinkamai pakeistas. Kadangi dvejetainėje paieškoje naudojamas surūšiuotas masyvas, elementą reikia įterpti tinkamoje vietoje. Priešingai, linijinei paieškai nereikia surūšiuoto masyvo, kad naują elementą būtų galima lengvai įterpti masyvo pabaigoje.

metodas

Linijinėje paieškoje elementui rasti naudojamas kartotinis metodas, todėl jis taip pat žinomas kaip nuoseklus metodas. Priešingai, dvejetainė paieška apskaičiuoja vidurinį masyvo elementą, todėl naudoja padalijimo ir užkariauk metodą.

Duomenų rinkinys

Sree Ramanujan

Linijinė paieška netinka dideliam duomenų rinkiniui. Jei norime ieškoti elemento, kuris yra paskutinis masyvo elementas, tiesinė paieška prasidės nuo pirmojo elemento ir tęsis iki paskutinio elemento, todėl elemento paieškai prireiks daug laiko. Kita vertus, dvejetainė paieška tinka dideliam duomenų rinkiniui, nes trunka mažiau laiko.

Greitis

Jei linijinėje paieškoje duomenų rinkinys yra didelis, skaičiavimo sąnaudos būtų didelės, o greitis sulėtėtų. Jei dvejetainėje paieškoje duomenų rinkinys yra didelis, skaičiavimo sąnaudos būtų mažesnės, palyginti su linijine paieška, o greitis tampa greitas.

Matmenys

Linijinė paieška gali būti naudojama tiek viename, tiek daugiamačiame masyve, o dvejetainė paieška gali būti įgyvendinta tik vienmačiame masyve.

Efektyvumas

Linijinė paieška yra mažiau efektyvi, kai atsižvelgiame į didelius duomenų rinkinius. Dvejetainė paieška yra efektyvesnė nei linijinė paieška didelių duomenų rinkinių atveju.

Pažvelkime į skirtumus lentelės pavidalu.