Dvejetainė paieška ir tiesinė paieška
Linijinė paieška, dar vadinama nuoseklia paieška, yra paprasčiausias paieškos algoritmas. Jis ieško nurodytos vertės sąraše, patikrindamas kiekvieną sąrašo elementą. Dvejetainė paieška taip pat yra metodas, naudojamas surasti nurodytą vertę surūšiuotame sąraše. Dvejetainės paieškos metodas perpus sumažina patikrintų elementų skaičių (kiekvienoje iteracijoje), sutrumpindamas laiką, per kurį nurodytas elementas surandamas sąraše.
Kas yra tiesinė paieška?
Linijinė paieška yra paprasčiausias paieškos metodas, kuris nuosekliai tikrina kiekvieną sąrašo elementą, kol randa nurodytą elementą. Linijinės paieškos metodo įvestis yra seka (pvz., Masyvas, rinkinys ar eilutė) ir elementas, kurio reikia ieškoti. Išvestis yra teisinga, jei nurodytas elementas yra pateiktoje sekoje, arba klaidingas, jei jis nėra sekoje. Kadangi šis metodas tikrina kiekvieną sąrašo elementą, kol bus rastas nurodytas elementas, blogiausiu atveju jis pereis visus sąrašo elementus, kol ras reikiamą elementą. Linijinės paieškos sudėtingumas yra o (n). Todėl manoma, kad jis yra per lėtas, kai naudojamas elementams ieškoti dideliuose sąrašuose. Bet tai labai paprasta ir lengviau įgyvendinama.
Kas yra dvejetainė paieška?
Dvejetainė paieška yra metodas, naudojamas nurodytam elementui rasti surūšiuotame sąraše. Šis metodas pradedamas lyginant ieškomą elementą su sąrašo viduryje esančiais elementais. Jei palyginus nustatoma, kad abu elementai yra lygūs, metodas sustoja ir grąžina elemento padėtį. Jei ieškomas elementas yra didesnis nei vidurinis elementas, jis vėl pradeda metodą, naudodamas tik apatinę surūšiuoto sąrašo pusę. Jei ieškomas elementas yra mažesnis nei vidurinis elementas, jis vėl pradeda metodą naudodamas tik viršutinę surūšiuoto sąrašo pusę. Jei ieškomo elemento nėra sąraše, metodas grąžins unikalią reikšmę, nurodančią tai. Todėl dvejetainės paieškos metodas perpus sumažina palyginamų elementų skaičių (kiekvienoje iteracijoje), atsižvelgiant į palyginimo rezultatą. Vadinasi,dvejetainė paieška vykdoma logaritminiu laiku, gaunant vidutinį o (log n) atvejį.
Kuo skiriasi dvejetainė paieška ir tiesinė paieška?
Nors tiek linijinė, 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 gali veikti ir nerūšiuotuose sąrašuose. Rūšiuojant sąrašą, vidutinis atvejų sudėtingumas yra n log n. linijinę paiešką yra paprasta ir paprasta įgyvendinti nei dvejetainę paiešką. Tačiau linijinė paieška yra per lėta, kad ją būtų galima naudoti su dideliais sąrašais dėl vidutinio o (n) atvejo našumo. Kita vertus, dvejetainė paieška laikoma efektyvesniu metodu, kurį būtų galima naudoti su dideliais sąrašais. Tačiau dvejetainės paieškos įgyvendinimas gali būti gana keblus ir tyrimas parodė, kad tikslią dvejetainės paieškos kodą galima rasti tik penkiose iš dvidešimties knygų.
