Dvejetainės ir linijinės paieškos skirtumas

Dvejetainė paieška palyginti su linijine paieška

Linijinė paieška, dar vadinama sekvencine paieška, yra paprasčiausias paieškos algoritmas. Jis ieško nurodytos vertės sąraše, tikrindamas kiekvieną sąrašo elementą. Dvejetainė paieška taip pat yra metodas, naudojamas nurodytai vertei rasti išrūšiuotame sąraše. Dvejetainis paieškos metodas sumažina patikrintų elementų skaičių (kiekvienoje iteracijoje), sumažindamas laiką, reikalingą nurodytam elementui rasti sąraše..

Kas yra linijinė paieška?

Linijinė paieška yra paprasčiausias paieškos būdas, kuriuo kiekvienas sąrašo elementas tikrinamas nuosekliai, kol jis randa nurodytą elementą. Įvestis į linijinį paieškos metodą yra seka (pvz., Masyvas, rinkinys ar eilutė) ir elementas, kurio reikia ieškoti. Išvestis yra tiesa, 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 praeis visus sąrašo elementus, kol suras reikiamą elementą. Linijinės paieškos sudėtingumas yra o (n). Todėl manoma, kad jis naudojamas per lėtai, kai ieškoma elementų dideliuose sąrašuose. Bet tai labai paprasta ir lengviau įgyvendinama.

Kas yra dvejetainė paieška?

Dvejetainė paieška taip pat yra būdas rasti nurodytą elementą išrūšiuotame sąraše. Šis metodas prasideda lyginant ieškomą elementą su elementais sąrašo viduryje. Jei palyginimas nustato, 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ę rūšiuoto sąrašo pusę. Jei ieškomas elementas yra mažesnis už vidurinį elementą, jis vėl pradeda metodą, naudodamas tik viršutinę rūšiuoto sąrašo pusę. Jei ieškomo elemento nėra sąraše, metodas grąžins unikalią reikšmę, nurodančią tai. Taigi dvejetainis paieškos metodas sumažina palyginamų elementų skaičių (kiekvienoje iteracijoje), atsižvelgiant į palyginimo rezultatą. Taigi dvejetainė paieška vykdoma logaritminiu laiku, gaunant o (log n) vidutinį atvejo našumą.

Kuo skiriasi dvejetainė ir linijinė paieška?

Nors tiek linijinė, tiek dvejetainė paieška yra paieškos metodai, jie turi keletą skirtumų. Nors dvejetainė paieška veikia išrūšiuotuose sąrašuose, linijinių laivų paieška gali veikti ir nerūšiuotuose sąrašuose. Rūšiavus sąrašą, vidutinis atvejo sudėtingumas yra n log n. Linijinę paiešką paprasta ir nesudėtinga įgyvendinti nei dvejetainę paiešką. Tačiau linijinė paieška yra per lėta, kad ją būtų galima naudoti dideliuose sąrašuose dėl jos o (n) vidutinio atvejo našumo. Kita vertus, dvejetainė paieška laikoma efektyvesniu metodu, kuris galėtų būti naudojamas turint didelius sąrašus. 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ų.