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 0thelementą ir nuskaito kiekvieną elementą, kol elementas, t. y. „E“, nerastas. Negalime tiesiogiai iššokti iš 0thelementas į 4thelementas, 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. 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 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. 
Linijinės ir dvejetainės paieškos skirtumai
Sree Ramanujan
Palyginimo pagrindas Linijinė paieška Dvejetainė paieška Apibrėžimas Linijinė paieška pradeda paiešką nuo pirmojo elemento ir lygina kiekvieną elementą su ieškomu elementu, kol elementas nerastas. Jis suranda ieškomo elemento padėtį, radęs vidurinį masyvo elementą. Surūšiuoti duomenys Atliekant linijinę paiešką, elementų nereikia rūšiuoti. Išankstinė dvejetainės paieškos sąlyga yra ta, kad elementai turi būti išdėstyti rūšiuota tvarka. Įgyvendinimas Linijinė paieška gali būti įgyvendinta bet kurioje linijinėje duomenų struktūroje, pvz., masyve, susietame sąraše ir kt. Dvejetainės paieškos įgyvendinimas yra ribotas, nes jis gali būti įgyvendintas tik tose duomenų struktūrose, kuriose yra dvipusis perėjimas. metodas Jis pagrįstas nuosekliu metodu. Jis pagrįstas „skaldyk ir valdyk“ principu. Dydis Pageidautina mažo dydžio duomenų rinkiniams. Pageidautina didelio dydžio duomenų rinkiniams. Efektyvumas Tai yra mažiau efektyvi didelių duomenų rinkinių atveju. Tai yra efektyvesnė didelio dydžio duomenų rinkinių atveju. Blogiausias scenarijus Atliekant tiesinę paiešką, blogiausias elemento radimo scenarijus yra O(n). Atliekant dvejetainę paiešką, blogiausias elemento radimo scenarijus yra O(log2n). Geriausias scenarijus Atliekant linijinę paiešką, geriausias scenarijus ieškant pirmojo elemento sąraše yra O(1). Dvejetainėje paieškoje geriausias scenarijus ieškant pirmojo elemento sąraše yra O(1). Matmenų masyvas Jis gali būti įgyvendintas tiek viename, tiek daugiamačiame masyve. Jį galima įgyvendinti tik daugiamačiame masyve.