Dvejetainė paieška vs linijinė paieška
Tiesinė paieška, taip pat žinoma kaip nuosekli paieška, yra paprasčiausias paieškos algoritmas. Jis ieško nurodytos reikšmės sąraše, patikrindamas kiekvieną sąrašo elementą. Dvejetainė paieška taip pat yra metodas, naudojamas norint rasti nurodytą reikšmę surūšiuotame sąraše. Dvejetainės paieškos metodas perpus sumažina patikrintų elementų skaičių (kiekvienoje iteracijoje), todėl sutrumpėja laikas, per kurį reikia rasti nurodytą elementą sąraše.
Kas yra linijinė paieška?
Tiesinė paieška yra paprasčiausias paieškos metodas, kuris tikrina kiekvieną sąrašo elementą paeiliui, kol randa nurodytą elementą. Linijinės paieškos metodo įvestis yra seka (pvz., masyvas, rinkinys arba eilutė) ir elementas, kurio reikia ieškoti. Išvestis yra teisinga, jei nurodytas elementas yra pateiktoje sekoje, arba klaidingas, jei jo nėra sekoje. Kadangi šis metodas tikrina kiekvieną sąrašo elementą, kol randamas nurodytas elementas, blogiausiu atveju jis pereis per visus sąrašo elementus, kol suras reikiamą elementą. Linijinės paieškos sudėtingumas yra o(n). Todėl manoma, kad jis yra per lėtas, kad būtų naudojamas ieškant elementų dideliuose sąrašuose. Tačiau tai labai paprasta ir lengviau įgyvendinama.
Kas yra dvejetainė paieška?
Dvejetainė paieška taip pat yra metodas, naudojamas norint rasti nurodytą elementą surūšiuotame sąraše. Šis metodas pradedamas lyginant ieškomą elementą su sąrašo viduryje esančiais elementais. Jei palyginus nustatoma, kad du elementai yra lygūs, metodas sustoja ir grąžina elemento padėtį. Jei ieškomas elementas yra didesnis už vidurinį elementą, metodas pradedamas iš naujo, naudodamas tik apatinę surūšiuoto sąrašo pusę. Jei ieškomas elementas yra mažesnis už vidurinį elementą, metodas pradedamas iš naujo, naudodamas tik viršutinę surūšiuoto sąrašo pusę. Jei ieškomo elemento sąraše nėra, metodas pateiks unikalią reikšmę, nurodančią tai. Todėl dvejetainis paieškos metodas perpus sumažina palyginamų elementų skaičių (kiekvienoje iteracijoje), priklausomai nuo palyginimo rezultato. Todėl dvejetainė paieška vykdoma logaritminiu laiku, todėl gaunamas o(log n) vidutinis atvejo našumas.
Kuo skiriasi dvejetainė paieška ir linijinė paieška?
Nors tiek tiesinė, tiek dvejetainė paieška yra paieškos metodai, jie turi keletą skirtumų. Nors dvejetainė paieška veikia surūšiuotuose sąrašuose, linijinė paieška taip pat gali veikti ir nerūšiuotuose sąrašuose. Sąrašo rūšiavimo atveju vidutinis atvejo sudėtingumas yra n log n. tiesinė paieška yra paprasta ir nesudėtinga įgyvendinti nei dvejetainė paieška. Tačiau linijinė paieška yra per lėta, kad ją būtų galima naudoti dideliuose sąrašuose dėl o(n) vidutinio atvejo našumo. Kita vertus, dvejetainė paieška laikoma efektyvesniu metodu, kuris gali būti naudojamas dideliuose sąrašuose. Tačiau dvejetainės paieškos įgyvendinimas gali būti gana sudėtingas, o tyrimas parodė, kad tikslų dvejetainės paieškos kodą galima rasti tik penkiose iš dvidešimties knygų.
