Binaarne otsing vs lineaarne otsing
Lineaarne otsing, tuntud ka kui järjestikune otsing, on lihtsaim otsingualgoritm. See otsib loendist määratud väärtust, kontrollides loendis kõiki elemente. Binaarne otsing on ka meetod, mida kasutatakse sorteeritud loendis määratud väärtuse leidmiseks. Binaarne otsingumeetod vähendab kontrollitud elementide arvu poole võrra (igas iteratsioonis), vähendades aega, mis kulub loendis antud üksuse leidmiseks.
Mis on lineaarne otsing?
Lineaarne otsing on lihtsaim otsingumeetod, mis kontrollib loendi iga elementi järjestikku, kuni see leiab määratud elemendi. Lineaarse otsingumeetodi sisendiks on jada (nt massiiv, kogum või string) ja üksus, mida tuleb otsida. Väljund on tõene, kui määratud üksus on etteantud jadas, või väär, kui seda jadas ei ole. Kuna see meetod kontrollib kõiki loendis olevaid üksusi kuni määratud elemendi leidmiseni, siis halvimal juhul läbib see kõik loendis olevad elemendid enne, kui vajaliku elemendi leiab. Lineaarse otsingu keerukus on o(n). Seetõttu peetakse seda suurtest loenditest elementide otsimisel kasutamiseks liiga aeglaseks. Kuid see on väga lihtne ja hõlpsamini rakendatav.
Mis on binaarne otsing?
Binaarne otsing on ka meetod, mida kasutatakse sorteeritud loendis määratud üksuse leidmiseks. See meetod algab otsitava elemendi võrdlemisega loendi keskel olevate elementidega. Kui võrdlus teeb kindlaks, et kaks elementi on võrdsed, peatub meetod ja tagastab elemendi asukoha. Kui otsitav element on suurem kui keskmine element, alustab see meetodit uuesti, kasutades ainult sorteeritud loendi alumist poolt. Kui otsitav element on väiksem kui keskmine element, alustab see meetodit uuesti, kasutades ainult sorteeritud loendi ülemist poolt. Kui otsitud elementi loendis ei ole, tagastab meetod kordumatu väärtuse, mis näitab seda. Seetõttu vähendab kahendotsingu meetod võrreldavate elementide arvu poole võrra (igas iteratsioonis), sõltuv alt võrdluse tulemusest. Järelikult töötab binaarne otsing logaritmilises ajas, mille tulemuseks on o(log n) keskmine juhtude jõudlus.
Mis vahe on binaarsel otsingul ja lineaarsel otsingul?
Kuigi nii lineaarne kui ka binaarne otsing on otsingumeetodid, on neil mitmeid erinevusi. Kui binaarne otsing toimib sorteeritud loendites, võib liiniotsing toimida ka sortimata loendites. Loendi sortimisel on juhtumite keskmine keerukus tavaliselt n log n. lineaarset otsingut on lihtne ja hõlpsam rakendada kui binaarset otsingut. Kuid lineaarne otsing on o(n) keskmise juhtumi jõudluse tõttu liiga aeglane, et seda suurte loendite puhul kasutada. Teisest küljest peetakse binaarset otsingut tõhusamaks meetodiks, mida saaks kasutada suurte loendite puhul. Kuid binaarotsingu rakendamine võib olla üsna keeruline ja uuring on näidanud, et kahekümnendotsingu täpset koodi võib leida vaid viiest raamatust kahekümnest.
